아이디어

• 경험치 보상이 작은 퀘스트부터 깨야 아케인 스톤에 최대한 많은 경험치를 누적시킬 수 있다.
• 각 퀘스트를 깬 후 경험치와 이전까지 보유한 아케인 스톤 개수의 곱들의 누적합이 정답

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tk = null;

	static int n, k;	// n: 퀘스트 수, k: 스톤 수
	static long[] exps;
	static long ans;	// a_i * n > 10^9
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		n = Integer.parseInt(tk.nextToken());
		k = Integer.parseInt(tk.nextToken());
		
		exps = new long[n];
		
		tk = new StringTokenizer(rd.readLine());
		for (int i=0; i<n; i++) {
			exps[i] = Long.parseLong(tk.nextToken());
		}
		
		Arrays.sort(exps);
		for (int i=0; i<k; i++) {
			ans += exps[i] * i;
		}
		for (int i=k; i<n; i++) {
			ans += exps[i] * k;
		}
		
		System.out.println(ans);
	}
}

메모리 및 시간

• 메모리: 57168 KB
• 시간: 824 ms

리뷰

• 각 작업의 대기 시간의 합을 최소로 하는 방법은 처리 시간이 가장 작은 작업부터 해결하는 것이라는 점에서 떠올렸다.