[Java] 백준(실버-4) 11399번 - ATM

문제 풀이

---

이번 문제는 그리디 알고리즘을 이용해 풀 수 있다.

아이디어 도출

중요하게 봐야할 부분은 바로 종료 시간이 아니라 대기 시간의 총합을 구하는 문제라는 점이다.

쉽게 생각해보면, 대기시간을 줄이기 위해선 앞사람이 일찍 끝나야 그만큼 최소로 하는 대기시간을 구하기 쉬워진다. 그리고 현재 차례에 사람이 인출할 때는 아무도 개입할 수 없다. 이 부분이 그리디 알고리즘의 조건인 독립성과 부분 최적해가 전체 최적해를 만족하게 된다.

결국, 입력받은 대기시간을 오름차순으로 정렬하여 대기시간을 구해주면 되는 활동 선택 문제 중 하나라고 볼 수 있다. 이때, 대기시간의 총합을 구하는 방법은 다음과 같다.

i번째 사람의 대기시간 + 이전까지의 대기시간 총합을 하면 i번째 사람이 대기한 시간을 구할 수 있다. 이 값을 result에 더해가면 모든 사람이 인출하는 걸린 대기시간의 총합을 구할 수 있게 된다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

class Main {    

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N+1];

        for(int i=1; i<=N; i++) {
            int P = Integer.parseInt(st.nextToken());
            arr[i] = P;
        }

        Arrays.sort(arr);

        int now = 0;
        int result = 0;

        for(int i=0; i<N; i++) {
            result += now + arr[i];
            now += arr[i];
        }
        
        bw.write(result+"\n");

        bw.close();
        br.close();
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.