Today's Algorithm(2019-03-12)

baekjoon11399. ATM

탐욕법에 대한 연습으로 뽑은 문제인데요. 사실 이 문제가 어떤 점에서 탐욕법인지 잘 모르겠습니다. 우선 문제를 풀 때 어떻게 하면 각 사람이 걸리는 시간을 최대한으로 줄일 것인가를 살펴봐야 하는데요. 그건 정렬에 있습니다. 만약 [1, 5, 3, 2, 4] 가 주어진다고 했을 때 3, 2, 4 걸리는 사람은 5를 다 더해주는 시간만큼 기다려야 합니다. 하지만 정렬이 되어 [1 2, 3, 4, 5]라면 큰 수를 더해주는 것을 피할 수 있겠죠. 결국 핵심은 빨리 끝날 사람은 먼저 끝내줘야 전체 기다리는 시간이 줄어든다는 것입니다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int answer = 0;
        int n = Integer.parseInt(br.readLine());
        int[] arr = toArray(br.readLine());
        Arrays.sort(arr);
        for (int i : arr) {
            answer += (i * n);
            n--;
        }
        System.out.println(answer);
    }

    private static int[] toArray(String line) {
        String[] arr = line.split(" ");
        int[] intArr = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            intArr[i] = Integer.parseInt(arr[i]);
        }
        return intArr;
    }
}