[Java] 백준 11399번 : ATM

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

11399번: ATM

[문제]

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM 앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는 데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [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과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는 데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

[출력]

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

[예제 입력]

[풀이 과정]

 이 문제는 돈을 인출하는데 걸리는 시간이 작은 순으로 사람들을 정렬시켜 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하면 된다.

 

1) 돈을 인출하는데 걸리는 시간이 작은 순으로 배열을 정렬시켜야 한다.

- Arrays.sort() 이용하여 정렬시켜도 되지만 Counting sort 방식으로 배열을 정렬시켜보았다.

 

2) 돈을 인출하는 데 걸리는 시간은  (1 ≤ Pi ≤ 1,000) 이기 때문에 배열의 크기를 1001로 잡았다. 배열의 인덱스를 돈을 인출하는데 걸리는 시간으로 보고,  해당하는 인덱스의 값에 +1 시켜준다. 

 

3) 반복문으로 배열을 돌면서 ( 0인 값은 넘어감) 대기시간 누적합을 갱신시키면서 현재 걸리는 시간을 더해주는 과정을 거치면 최종적으로  총 대기 시간을 구할 수 있다.

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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()); //줄 서 있는 사람의 수

        int[] array = new int[1001]; //counting sort

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

        int before=0; //대기시간 누적합
        int sum=0; //총 대기 시간


        for (int i = 0; i < N; i++) {
            array[Integer.parseInt(st.nextToken())]++;
        }

        for (int i = 0; i < 1001; i++) {
            while (array[i]-- > 0) {
                sum+=before+i; //대기 시간 누적합 + 현재걸리는 시간
                before +=i; //대기 시간 누적합 갱신

            }

        }
        System.out.print(sum);

    }
}

[결과]