백준/11399 ATM

작성일 | In

< 문제 분석 및 풀이 방법 >

Backjoon :: ATM 문제는 오름차순 정렬 후 값을 더해가면 된다.

  • 오름차순이 필요한 이유는 대기시간이 짧은 사람부터 해결하는 것이 뒤에 사람들이 기다리는 시간이 최소가 되기 때문이다.
  • Java의 경우 Arrays.sort로 정렬해도 되지만, MergeSort 구현 연습도 할 겸해서 합병정렬로 정렬했다.
  1. 입력받은 배열을 Arrays.sort 또는 MergeSort로 오름차순 정렬한다.
  2. 각 idx 마다 기다리는 시간을 더해주면서 값을 구한다.

< 소스 코드 >

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.io.*;
import java.util.*;

public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[] sort;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        sort = new int[n];
        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(stk.nextToken());
        }
        merge(arr, 0, n - 1);   //1. 정렬
        int ans = 0, sum = 0;   //2. 각 idx 마다 기다리는 시간을 더해준다.
        for (int i = 0; i < n; i++) {
            sum += arr[i];
            ans += sum;
        }
        System.out.println(ans);
    }

    public static void merge(int[] arr, int start, int end) {
        if (start < end) {
            int mid = (start + end) / 2;
            merge(arr, start, mid);
            merge(arr, mid + 1, end);
            mergeSort(arr, start, mid, end);
        }
    }

    public static void mergeSort(int[] arr, int start, int mid, int end) {
        int left = start;
        int right = mid + 1;
        int idx = start;
        while (left <= mid && right <= end) {
            if (arr[left] < arr[right]) {
                sort[idx++] = arr[left++];
            } else {
                sort[idx++] = arr[right++];
            }
        }
        while (left <= mid) sort[idx++] = arr[left++];
        while (right <= end) sort[idx++] = arr[right++];
        for (int i = start; i <= end; i++) {
            arr[i] = sort[i];
        }
    }
}