백준 11399 ATM - JAVA

11399 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int input = Integer.parseInt(br.readLine());
        int[] arr = new int[input];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for (int i = 0; i < input; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(arr);
        
        int time = 0;
        int sum = 0;
        for(int i = 0; i < input; i++) {
            time += arr[i];
            sum += time;
        }
        
        bw.write(String.valueOf(sum));
        bw.flush();
    }
}

 

알고리즘 설명

---

그리디 알고리즘이란, 현재 상황에서 가장 최적의 선택을 반복적으로 선택하는 해결책을 구하는 알고리즘으로,
문제 해결을 효율적으로 해결할 수 있도록 돕는 알고리즘입니다.
 
해당 문제에서 최적의 선택은, 모든 대기인원의 평균 대기시간을 줄여주는 방식을 채택할 수 있습니다.
스케줄링 알고리즘을 알고 계신분들은 쉽게 생각하셨을텐데요,
바로 평균 대기시간을 낮추는 SJF(Shortest Job First)에 맞게, 실행시간이 짧은 숫자를 앞으로 배치하는 것입니다.
 
각 인원의 대기시간은, 앞선 모든 인원들의 인출시간을 합산한 것과 같기 때문에,
총 소요시간은, 1번 원소부터 마지막 원소까지, 각 원소의 인출시간과 대기시간을 더하여 누적합 계산을 하면 쉽게 계산할 수 있습니다.

 

코드 해석

---

입력 받은 인출시간을 배열에 저장하고, 인출시간이 짧은 것부터 오름차순으로 정렬합니다. 인원별 인출시간과 대기시간을 모두 합산해야 하기때문에, 각 인원의 총 소요시간(인출시간 + 대기시간)을 담아줄 time변수와 총 인원의 총 소요시간을 담아줄 sum변수를 선언하고, 각 작업마다 time의 값을 sum에 누적합 해줍니다.