[BOJ] 11399 - ATM

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/11399

11399번: ATM

난이도: 실버 3

사용언어: JAVA

 

풀이

필요한 시간의 합을 최소화하기 위해서는 당연히 짧게 걸리는 순서대로 연산을 수행하면 됩니다. 즉 입력을 한 배열에 담고 해당 배열을 오름차순으로 소팅하여 총시간을 계산해주면 됩니다. 

 

예를 들어, 1 2 3 4 ... 순서로 줄을 서 있다면,

 

1이 인출을 하기 위해 기다려야 하는 시간은 1초

2가 인출을 하기 위해 기다려야 하는 시간은 1+2 = 2초

3이 인출을 하기 위해 기다려야 하는 시간은 1+2+3 = 6초

4가 인출을 하기 위해 기다려야 하는 시간은 1+2+3+4 = 10초 ...

이므로 총 기다려야 하는 시간의 합은 (1+(1+2)+(1+2+3)+(1+2+3+4)+...)이 됩니다.

 

즉 앞에 있는 수가 연산에 가장 많이 포함되기 때문에 작은 순서대로 줄을 세워서 인출을 하면 최소 시간을 구할 수 있습니다.

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
 
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 N = Integer.parseInt(br.readLine());
        int i;
        StringTokenizer st = new StringTokenizer(br.readLine());
        int []arr = new int[N+1]; // 입력 값을 저장할 배열
        int sum = 0;
        for(i=1;i<=N;i++)
            arr[i] = Integer.parseInt(st.nextToken());
       Arrays.sort(arr); // 소팅
        for(i=1;i<=N;i++){ // 가장 작은 수 부터
            arr[i] += arr[i-1]; // 각 사람별로 기다려야 하는 시간을 구하고
            sum+=arr[i]; // 총 합을 구해줌
        }
        bw.write(String.valueOf(sum));
        bw.flush();
    }
}