[Algorithm] 99클럽 코테 스터디 17일차 TIL | 백준_ATM(11399번)

📝문제

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

 

💡풀이

모든 사람이 돈을 인출하는데 필요한 시간을 최적화하기 위해서는 시간이 적게 걸리는 사람부터 처리하면 된다.

현재 상황에서의 최적의 값을 선택하면 전체 최적의 해가 된다 => 그리디 알고리즘

 

각 사람이 돈을 인출하는데 걸리는 시간을 오름차순으로 정렬 후 

시간의 합을 구해준다.

 

전체 풀이

import java.util.*;
import java.io.*;
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[] time = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            time[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(time);

        for(int i = 1; i < N; i++){
            time[i] += time[i-1];
        }

        int answer = 0;
        for(int t : time){
            answer += t;
        }

        System.out.println(answer);
    }
}

 

🤔Review

99클럽을 진행하며 가장 빠르게 푼 문제 같다. 그리디 알고리즘이라고 생각 후 문제에 접근했는데 이후에 문제만 보고 그리디 알고리즘을 떠올릴 수 있게 연습이 필요하다.