알고리즘 풀이 - 백준 11399(ATM, 그리디(Greedy))

 

관련글

 

그리디 알고리즘 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

1대의 ATM에 N명의 사람이 줄을 섰을 때, m번째 사람이 돈을 인출 시 걸리는 시간은 Pm이라고 하면 모든 사람이 대기 시간을 합쳐 모두 돈을 인출 시에 걸리는 최소의 시간을 구하는 문제

 

 

2. 풀이

 

이 문제는 그리디로 해결 가능한 제일 쉬운 수준의 문제이다.

전체 대기 + 인출까지 모든 인원이 수행할 수 있도록 합이 최소가 되려면 뒤의 사람이 걸리는 시간이 최소가 되어야만 한다. 

예를 들어 아래를 보자. 인원이 3명이 있을 때, 각 인원이 인출 시 걸리는 시간은 다음과 같다.

사람 3명 - 10, 6, 4

 

그러면, 오래 걸리는 사람이 앞에 있으면 뒤의 사람들은 대기 시간이 그만큼 추가되기 때문에 대기 시간을 최대한 줄이려면 짧게 걸리는 사람을 앞에 두어야 한다.

내림차순 정렬 시의 총 걸리는 시간 : 10 + 16 + 20 = 46
오름차순 정렬 시의 총 걸리는 시간 : 4 + 10 + 20 = 34

 

즉, 위와 같이 정렬을 수행한 뒤 대기 시간 + 인출 시간을 구해 더해주면 문제를 해결할 수 있다.

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

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

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[] list = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i < n; i++){
            list[i] = Integer.parseInt(st.nextToken());
        }
        
        // 짧게 걸리는 순서로 오름차순 정렬 수행한다.
        Arrays.sort(list);
        
        // 기다린 시간 만큼 전체 정답에 더한다.
        int ans = 0;
        int wait = 0;
        for(int i=0; i < n; i++){
            wait += list[i];
            ans += wait;
        }
        System.out.println(ans);
        br.close();
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.