BOJ(백준 온라인 저지) 11399번 with 자바[JAVA]

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

11399번: ATM

---

문제를 보자

 

사람의 수가 주어지고 각 사람이 인출하는데 걸리는 시간을 다음 줄에 준다.

이때 사람의 순서를 잘 배치하여 각 사람이 돈을 인출하는데 걸리는 시간이 최소가 되는 시간을 계산하면 된다.

 

각 사람이 인출하는데에 걸리는 시간이 최소가 되려면 어떻게 해야할까?

 

문제에 주어진 예시를 보자

 

P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 일 때 최소 시간이 소요되는 순서는

[2, 5, 1, 4, 3] 이다.

 

이는 각 사람이 인출하는데에 걸리는 시간의 오름차순이다.

 

왜 오름차순 순서로 해야 최소시간이 될까?

 

문제의 정답을 재정의해보자.

 

F 를 본인이 돈을 인출하기까지 걸린 시간이라고 하자.

위에 최소 소요시간인 순서의 경우를 생각하자.

F2(* 1번 사람이 인출하는데 걸리는 시간) 은 1분이다. 앞사람이 없어서 기다리지 않고 바로 인출하면 되기 때문이다.

 

F5(* 5번 사람이 인출하는데 걸리는 시간) 은 3분이다. 앞사람(* 2번)을 기다리고 인출하면 된다.

이때 3분은 F2 + P5 이다.

 

F1 은 6분이다. 앞사람 두 명을 기다리고 인출하면 된다.

이때 6분은 F2 + F5 + P1 이다.

 

...(규칙이 보인다.)....

 

결국 정답은 F2 + F5 + F1 + F4 + F3 이다.

 

따라서,

 

리스트에 각 사람의 P 를 저장하고,

오름차순으로 정렬한 다음,

누적합을 하고,

그것들의 합을 구하면 된다.

 

코드를 보자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] list = new int[N];

        for(int i=0; i<N; i++) // P 리스트
        {
            list[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(list); // 오름차순 정렬

        for(int i=1; i<N; i++) // 누적힙
        {
            list[i] += list[i-1];
        }

        int sum = 0;

        for(int i=0; i<N; i++) // 누적합의 합
        {
            sum += list[i];
        }

        System.out.println(sum);
    }
}

---

• 느낀 점

...