개요

백준 1715: 카드 정렬하기

• 입력
  첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

• 출력
  첫째 줄에 최소 비교 횟수를 출력한다.

접근방식

1. 제일 작은값들을 더해가며 푸는 그리디 방식인건 알 수 있었지만, 단순히 priority_queue가 empty일까지 top값들을 누적해서 더하며 답을 구했더니 틀렸다.

2. 이유는 제일 작은값들을 더해야 하기 때문이다.

   예를 들어 카드 묶음이 네개가 있고 6 7 8 9 이렇게 존재한다면,
   내 방식대로 구현한다면 6+7 = 13, 13 +8= 21, 21+9= 30 /
   총 답은 13+21 + 30으로 64다.

   하지만 답은 6+7= 13, 8+9=17, 13+17= 30 /
   13+17+30= 60이다.

3. 이처럼 제일 작은 값 두개를 더한 값과 그다음 작은 값을 더하는 방식이 무조건 답이라고 볼 수 없으므로,
   제일 작은 값 두개를 더한 값을 다시 priority_queue에 넣는 방식으로
   구현해야한다.

전체 코드

#include<queue>
#include<vector>
#include<iostream>

using namespace std;
priority_queue<int, vector<int>, greater<int>> pq;

void Solution() {
	int Ans = 0,tmp=0;
	//카드 뭉치 한개라면 비교횟수는 0회
	if (pq.size() == 1) {
		cout << 0 << '\n';
		return;
	}
	//사이즈가 1이 아닐때 
	while (pq.size() != 1) {
		//우선순위큐에서 top값 두개를 빼서 더한다.
		for (int i = 0; i < 2; i++) {
		tmp += pq.top();
		pq.pop();
		}
		//더한 값을 다시 우선순위큐에 넣기
		pq.push(tmp);
		//더한값을 Ans변수에 더해줌 
		Ans += tmp;
		tmp = 0;
	}
	cout << Ans;
	return;
}

void Input() {
	int N=0,tmp=0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		pq.push(tmp);
	}

}

int main() {
	Input();
	Solution();
}

문풀후생

[백준 질문 게시판 링크]
이 링크에서 결정적으로 틀린 부분을 찾았다.