[문제 풀이] 백준 11399번 ATM JAVA

문제

 

  문제접근 방법   

해당 문제는 atm이 한대 밖에 없고 1번 부터 N번까지 줄을서 돈을 인출하는데 각각 인출하는데 필요한 시간이다르다.

이때 모든 사람이 돈을 인출하는데 필요한 시간의 최솟값을 출력하는 문제이다.

여기서 1번에 돈을 인출하는데 3만큼걸리면 나머지 2~N까지는 2분을 기다리는것을 감안해 걸리는 시간을 계산한다.

예를 들어 1 2 3번 이있고 각각 3 2 1 이라면 순서대로 인출시 1번 3, 2번은 3 기다리고 2 = 5, 3은 5기다리고 1 =6

3+5+6=18 이 소요되는 것이다.

해당 문제도 그리디 알고리즘을 사용하면 풀이가 가능할 것이라 판단하였다. 앞서 동전 0문제에서 그리디는 

지금 당장 제일 좋은 선택을 하는 것인데 여기서 가장 먼저 인출하는 사람의 소요시간이 길면 길수록 큰값이 누적되어 총 필요한 시간의 합이 늘어난다. 그래서 가장 좋은 선택은 소요시간이 작은 사람부터 인출을 하면 최솟값을 출력할 수 있겠다고 생각했다.

 

< 최종 코드 >

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int arr[]=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=s.nextInt();
        }
        
        Arrays.sort(arr);
        int sum=arr[0];
        for(int i=1;i<n;i++){
            arr[i]=arr[i-1]+arr[i];
            sum+=arr[i];
        }
        System.out.print(sum);
    }
}

가장 작은 인출시간을 소요하는 사람이 가장 앞에서 일을 해결해야하므로 정렬을 통해 오름차순으로 만들어주고 더해 출력하는 방식으로 구현하였다.

 

  마무리  

아직 최적의해, 정당성 이런 근거들이 확실하고 명확하게 떠오르거나 보이지는 않지만 어떤식으로 사용하는지에대한 

감은 잡아 문제를 더 경험하고 풀어봐야겠다.