백준 11399번 ATM

ATM은 ATM 앞에 줄 선 사람들의 순서를 조작해 모두가 은행업무를 마칠 수 있는 최소한의 시간을 구하는 문제다.

(선두에 줄을 선 사람에는 손해일 수도 있으며, 손해 여부를 떠나 현실에서는 결코 일어날 수 없는 일이다..)

 

주어진 문제 설명에 따르면 사람에 따라 각각 다음과 같은 시간이 소요된다고 한다.

Person 1	Person 2	Person 3	Person 4	Person 5
3 분	1 분	4 분	3 분	2 분

 

업무 처리에 개인이 소요하는 시간은 순서에 따라 상관없이 일정하지만, 뒤에 서 있을 수록 앞 사람들이 일을 모두 마칠 때까지 기다려야 하므로 실제로 업무 처리에 소요되는 시간은 다음과 같으며 총 39분이 소요된다.

Person 1	Person 2	Person 3	Person 4	Person 5
3 분	(3+1 = 4) 분	(3+1+4 = 8) 분	(3+1+4+3 = 11) 분	(3+1+4+3+2 = 13) 분

 

전체 업무 처리 시간을 최소화할 수 있는 방법은 무엇일까? 특정 수열을 누적하고, 그 누적 값을 모두 더했을 때 최소값을 만들기 위해서는 누적 값을 최소화해야 한다. 누적 값은 수열이 오름차순으로 정리되어 있을 때 가장 작다.

 

따라서, 업무 처리 시간이 짧은 사람부터 오래 걸리는 사람 순으로 나열하고 그 값을 누적하면 총 소요 시간의 최소값을 얻을 수 있다. 이럴 경우 소요 시간은 총 32분이다.

	Person 2	Person 5	Person 1	Person 4	Person 3
개인별 소요시간	1 분	2 분	3 분	3 분	4 분
누적 소요시간	1 분	3 분	6 분	9 분	13 분
총 소요시간	1 분	4 분	10 분	19 분	32 분

 

일련의 과정들을 코드로 구현하였다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int N = in.nextInt();

        // 개인별 소요시간
        int[] persons = new int[N];
        for (int i = 0; i < N; i++) {
            persons[i] = in.nextInt();
        }

        Arrays.sort(persons);

        int pSum = 0; 
        int total = 0; 

        for (int i = 0; i < N; i++) {
            pSum += persons[i]; // 누적 소요시간
            total += pSum; // 총 소요시간
        }

        System.out.println(total);
    }
}