[C++]백준 1715번: 카드 정렬하기

문제

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

문제이해

 

• 첫째 줄에 N이 주어집니다.
• 두 번째 줄부터 N개만큼의 카드 묶음을 입력합니다.
• 최소 비교 횟수를 출력합니다.

 

이 문제에서 주목해야 하는 부분은 바로 숫자 카드 묶음이 한 개만 남기 전까지 모든 카드를 묶는다는 것입니다. 카드 묶음과 카드 묶음을 묶어 새로운 카드 묶음을 만들고 이 새로운 카드 묶음은 다시 다른 카드묶음과 합쳐지게 됩니다. 간단하게 말하자면 카드 묶음이 재활용된다는 것인데 재활용 되는 카드 묶음의 크기가 작을수록 비교 횟수가 적어지게 됩니다.

 

예시를 들어보겠습니다.

10 20 40

카드 묶음이 다음과 같이 총 3개 존재하며 각각의 값은 20, 30, 50 입니다. 이 3개의 카드 중 2개의 카드를 서로 묶어 만들 수 있는 카드 묶음은 10 + 20 또는 20 + 40 또는 10 + 40이 있습니다. 위에 말했던 것처럼 묶음이 재활용되기 때문에 각각 30, 60, 50이 재활용이 됩니다. 결과적으로 비교 횟수는 각각 70 + 30, 70 + 60, 70 + 50 이 되게 될 것이고 최솟값은 70 + 30 = 100이 나오게됩니다. 

 

이를 통해 재활용 되는 값이 최솟값이 되도록 해야 합니다. 따라서 카드 묶음들을 정렬 기준이 오름차순인 우선순위 큐에 넣고 두개씩 빼내어 합을 더해 그 값을 다시 우선순위 큐에 넣어주면 됩니다. 이를 우선순위 큐의 크기가 1이 될때까지 반복하게 되면 마지막으로 우선순위 큐에 남아있게 되는 원소의 크기가 정답이 되게 됩니다.

 

다음은 위의 설명대로 만들어진 코드입니다.

 

문제풀이

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

priority_queue<int, vector<int>, greater<int>> nums;

void result() {
	int p{ 0 };
	while (nums.size() != 1) {
		int top = nums.top();
		nums.pop();
		top += nums.top();
		nums.pop();
		nums.push(top);
		p += top;
	}
	cout << p;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N, X;
	cin >> N;
	for (int i{ 0 }; i < N; i++) {
		cin >> X;
		nums.push(X);
	}
	result();
}

 

문제후기

문제의 핵심을 생각하는 게 어렵지 않은 문제였습니다.