[백준-11399]-[그리디알고리즘]-ATM

문제 링크 : https://www.acmicpc.net/problem/11399

이문제는 아주 쉽게 계산했다.

최선과 최악의 경우의 수만 설명하면 어떻게 풀지 감이 올것이다.

5
3 1 4 3 2

위와 같이 입력이 되고 각 사람별 인출하는 시간이 3, 1, 4, 3, 2 라고 한다.

1번 사람은 3분

2번 사람은 1분

3번 사람은 4분

4번 사람은 3분

5번 사람은 2분

i 번 사람이 인출하는데 걸리는 시간은 i - 1번 사람이 걸린 시간에 i 사람이 인출하는데 소요되는 시간이다. 

아래에 최악과 최선의 순서를 보면 어떻게 풀어야 할지 감이 온다.

최악

3번, 1번, 4번, 5번, 2번 순으로 인출을 한다.

3번 사람은 4분

1번 사람은 4 + 3 = 7분 

4번 사람은 7 + 3 = 10분

5번 사람은 10 + 2 = 12 분

2번 사람은 12 + 1 = 13분

총 합해서 45분이 걸린다.

최선

2번, 5번, 1번, 4번, 3번 순으로 인출한다.

2번 사람은 1분

5번 사람은 3분

1번 사람은 6분

4번 사람은 9분

3번 사람은 13분

총 합해서 32분 걸린다.

즉 이문제는 인출하는데 걸리는 시간이 제일 적은 사람부터 인출하게 되면 모두 인출하는데 걸리는 시간은 최소가 된다고 이해하고 풀면 된다.

입력받은 시간 정보를 배열에 저장하고 배열을 오름차순으로 정렬 한뒤 순서대로 소요시간을 계산하면 끝난다.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class B_11399 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int cnt = Integer.parseInt(st.nextToken());
        
        int[] arr = new int[cnt];
        st = new StringTokenizer(br.readLine());
        
        for(int i=0; i < cnt; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        
        int result = 0;
        int sum = 0;
        for(int time:arr) {
            sum = sum + time;
            result += sum;
        }
        System.out.println(result);
    }
 
}