BOJ11399 ATM

https://www.acmicpc.net/problem/11399 (opens new window)

인하은행에는 ATM이 1대 밖에 없다. 사람은 1번 부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi 분 이다.

사람들이 줄을 서는 순서에 따라 돈을 인출하는데 필요한 시간의 합이 달라진다. 줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구한다.

제출 코드

정렬을 진행한다. Java는 기본적으로 오름차순 정렬된다. 최솟값을 구하기 위해서는 시간이 적게 걸리는 사람이 먼저 돈을 인출해야 한다.

Arrays.sort(array);

int sum = 0;
for (int i = 0; i < n; i++) {
    sum += array[i] * (n - i);
}

아래는 최종 제출 코드이다.

public class BOJ11399 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] array = new int[n];

        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }

        Arrays.sort(array);

        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += array[i] * (n - i);
        }

        System.out.println(sum);
    }
}

#algorithm #BOJ #그리디 알고리즘 #정렬