백준 카드 합체 놀이(15903)

카드 합체 놀이

1. 힌트

1) 합체를 한 번 할때마다 카드는 사라지지 않고 점수는 $S[x] + S[y]$만큼 늘어납니다.

2) 가장 값이 작은 카드 두 개를 골라서 합치는 것이 무조건 이득입니다.

3) 계산 결과가 32비트 정수형의 범위를 넘을 수 있습니다.

2. 접근

1) 수식으로 표현할 수 있을까?

$S[x]$와 $S[y]$를 골라서 합체하면 수열의 총 합은 어떻게 될까요? $S[x]$에 쓰여진 값은 $S[x] + S[y]$로 변하고, $S[y]$에 쓰여진 값은 $S[y] + S[x]$로 변합니다. 수식으로 나타내면 이와 같습니다.
$(S[x], S[y]) \to (S[x] + S[y],\ S[y]+S[x])$

수열의 합은 기존에서 $S[x] + S[y]$만큼 늘어나는 것을 알 수 있습니다.
어떤 카드를 고르더라도 둘 중 어느 카드도 사라지지 않으므로 언제나 가장 작은 것 만을 그리디하게 고르면 점수를 최소화 할 수 있습니다.

3. 구현

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		PriorityQueue<Long> pq = new PriorityQueue<>();
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) pq.offer(Long.parseLong(st.nextToken()));
		for (int i = 0; i < M; i++) {
			long t = pq.poll() + pq.poll();
			pq.offer(t); pq.offer(t);
		}
		long sum = 0;
		for (long x : pq) sum += x;
		System.out.println(sum);
	}

}