boj 11399 ATM

www.acmicpc.net/problem/11399

11399번: ATM

N명의 사람이 줄을 서는데 순서대로 돈을 인출하는데 걸리는 시간이 주어집니다.

 

[1, 2, 3]의 순서대로 줄을 서고 인출하는데 걸리는 시간이 [a, b, c]라고 하면

 

1이 먼저 인출하면 2, 3은 a만큼의 시간을 기다리게 됩니다.

그 다음 2가 인출하면 3은 b만큼의 시간을 더 기다려서 총 a+b만큼을 기다립니다.

 

줄을 어떻게 서냐에 따라 총 기다리는 시간이 달라지는데, 이를 최소화하여 모든 사람이 돈을 인출하는데 필요한 시간을 최소로 해야합니다.

 

기다리는 시간을 최소로 하기 위해서는 인출하는 시간이 적은 사람이 먼저 하면 됩니다.

저는 인출하는 시간을 오름차순으로 정렬하였고, dp로 간단하게 구현하였습니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[], dp[];
    static int N, ans;
 
    static void solve() {
        for (int i = 1; i <= N; i++) {
            dp[i] = dp[i - 1] + list[i];
            ans += dp[i];
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N + 1];
        dp = new int[N + 1];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(list);
    }
 
    public static void main(String[] args) throws Exception {
        input();
        solve();
    }
}