[백준(baekjoon) 11399] ATM

문제

백준 11399

N(1…1000)명의 사람이 돈을 인출하는데 걸리는 시간 Pi(1…1000) 이 각각 주어진다고 할 때,
각 사람이 돈을 인출하는데 필요한 시간의 합의 최소값을 구하시오.

• 주의 : i번째 사람이 돈을 인출하는데 필요한 시간은 1...i-1번째 사람을 기다리는 대기 시간도 포함한다.
• 예시 : P1 = 3, P2 = 1, P3 = 4일 때,
  [1, 2, 3]순서로 돈을 뽑을 때는 3 + (3 + 1) + (3 + 1 + 4) = 15의 시간이 걸린다.
  [2, 1, 3]순서로 돈을 뽑아야 1 + (1 + 3) + (1 + 3 + 4) = 13인 최소값이 나온다.

해결

아주 쉬운 문제이다. 대기시간을 줄이는게 관건이다.
즉, 시간을 오름차순으로 정렬하여 앞에서 부터 사용 시간 = 이전 값(대기 시간) + 자신의 값(이용 시간)을 구하고 각 사용시간을 모두 더해주면 끝.

알고리즘

그리디 알고리즘을 사용해 해결하였다.
이용시간이 짧은 사람부터 하면 된다고 가정하였고, 그 증명이 가능했기 때문.

그리디 알고리즘에 대해 잘 모르신다면 이 글을 참고하세요!

구현 java

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.
7.        int n = sc.nextInt();
8.        int[] array = new int[n];
9.        for (int i = 0; i < n; i++)
10.            array[i] = sc.nextInt();
11.
12.        Arrays.sort(array);
13.        int sum = array[0];
14.        for (int i = 1; i < n; i++) {
15.            array[i] += array[i - 1];
16.            sum += array[i];
17.        }
18.        System.out.println(sum);
19.    }
20.}

결과