백준 11399 ATM [JAVA]

문제 해석

• 첫째 줄에 사람의 수(N)을 입력 받고, N번 만큼 각 사람이 돈을 인출하는 데 걸리는 시간 P¡ 을 입력받는다.
• 모두 입력받았으면 사람의 배치를 다르게 하여 최소 필요 시간을 구하면 된다.
  

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine()); //총 사람 수

        int[] schedule = new int[N]; // 사람 횟수

        st = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++){
            schedule[i] =  Integer.parseInt(st.nextToken()); //시작 시간
        }

        br.close();

        Arrays.sort(schedule); //배열 정렬 (적은 시간 -> 큰 시간)

        int[] preSum = new int[N]; //시간을 누적합해서 저장할 배열

        preSum[0] = schedule[0];
        int result = preSum[0]; //총 최소 시간을 넣는 배열

        for(int i = 1; i < schedule.length; i++){
            preSum[i] = preSum[i-1] + schedule[i]; //누적합
            result += preSum[i]; //총 최소 시간
        }

        System.out.println(result);

    }
}

결과

느낀 점

이 문제는 크게 어려움없이 금방 풀 수 있는 문제였다. 문제를 읽다보니 자연스럽게 정렬을 해야겠다는 생각이 들었고, 무작정 더하는 것보다 누적합이 더 효율적일 것 같아서 딱딱 그냥 풀 수 있는 문제였다.