[백준] #11399 ATM

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

🔒문제 설명

ATM이 한대밖에 없는 은행이 있습니다. 그리고, 돈을 인출하기 위해 줄을 서 있는 사람은 모두 N명입니다. i번째 사람이 돈을 인출하는 시간 $P_i$가 주어질 때, 사람들이 모두 돈을 인출하는데 필요한 최소 시간을 구하세요.

🔑해결 아이디어

임의의 순서로 정렬 된 후 $i$번째 사람이 돈을 인출하는 데 걸리는 시간은 $\sum^i_{k = 1}P_k$ 이다.
즉, 모든 사람이 전부 돈을 인출하는 데 걸리는 시간은 $\sum^N_{i= 1}\sum^i_{k = 1}P_k$ 입니다.
따라서 시간이 적게 걸리는 사람을 앞 순서에 정렬 하는것이 시간을 줄일 수 있는 방법입니다.

시간이 적게 소요되는 사람을 앞에 정렬 한 후, 소요되는 총 시간의 합을 구합니다.

💻소스코드

import java.util.*;

public class BJ11399 {
    public static void main(String[] args) {
    
        Scanner sc = new Scanner(System.in);
        int sum = 0;
        int person = sc.nextInt();
        LinkedList<Integer> list = new LinkedList<>();
        
        //배열 입력
        for (int i = 0; i < person; i++) {
            list.add(sc.nextInt());
        }
        
        //Collection 정렬
        Collections.sort(list);

		//i번째 사람이 돈을 인출하는 데 걸리는 시간 P_i 구하기
        for (int i = 0; i < person-1; i++) {
            int cur = list.remove(i+1);
            list.add(i+1, cur + list.get(i));
        }

		//총 시간 구하기
        for(int num : list)
            sum += num;

        System.out.println(sum);
    }
}