[BOJ/Greedy] 백준 11399 - ATM (Java)

11399 - ATM

https://www.acmicpc.net/problem/11399

문제

인하은행 ATM 1대, N명의 사람들이 줄 서 있음
사람은 1번 ~ N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 $P_i$분
사람들이 줄을 서는 순서 -> 돈을 인출하는데 필요한 시간의 합이 달라짐

ex. 총 5명, $P_1=3, P_2=1, P_3=4, P_4=3, P_5=2$ 인 경우,
1. [1, 2, 3, 4, 5] 순서로 줄을 선다면
1번 사람: 3분만에 돈을 뽑을 수 있음
2번 사람: 1번 사람이 돈을 뽑을 때까지 기다려야 함 -> 3 + 1 = 4분
3번 사람: 3 + 1 + 4 = 8분
4번 사람: 3 + 1 + 4 + 3 = 11분
5번 사람: 3 + 1 + 4 + 3 + 2 = 13분
-> 각 사람이 돈을 인출하는데 필요한 시간의 합: 3 + 4 + 8 + 11 + 13 = 39분
2. [2, 5, 1, 4, 3] 순서로 줄을 선다면
2번 사람: 1분
5번 사람: 1 + 2 = 3분
1번 사람:  1 + 2 + 3 = 6분
4번 사람: 1 + 2 + 3 + 3 = 9분
3번 사람: 1 + 2 + 3 + 3 + 4 = 13분
-> 각 사람이 돈을 인출하는데 필요한 시간의 합: 1 + 3 + 6 + 9 + 13 = 32분

=> 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값

입력
첫째 줄: 사람의 수 N (1 <= N <= 1,000)
둘째 줄: 각 사람이 돈을 인출하는데 걸리는 시간 $P_i$ (1 <= $P_i$ <= 1,000)
출력: 각 사람이 돈을 인출하는데 필요한 사건의 합의 최솟값

---

풀이

• Arrays.sort(P);
  • 시간이 짧은 사람부터 인출 -> 전체 기다리는 시간 최소

---

코드

import java.io.*;
import java.util.*;

// ATM
public class boj_11399 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] P = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            P[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(P);

        int sum = 0;
        int total = 0;
        for (int p : P) {
            sum += p;
            total += sum;
        }

        System.out.println(total);
    }
}