[C++] BOJ 1715번 - 카드 정렬하기

📖 Problem

---

🔓 Solve

---

이 문제를 보고 처음 생각한 방식은, 각 단계마다 가장 작은 수들을 합쳐가는 것이다.

이렇게 각 단계마다 최선의 선택을 하는 알고리즘을 그리디 알고리즘 이라고 한다.

풀이를 하면서 실수를 한 부분이 있는데, 각 경우마다 모든 묶음에서 최소값 두개를 선택 해야 하는 점이었다.

이게 무슨 의미인가 하면

1. 10 10 10 10 40 50 과 같이 카드 묶음이 주어졌다고 하자.

2. 이 때 처음에 10과 10을 골라서 20을 만들 것이다.

3. 이러면 카드 묶음은 10 10 20 40 50 으로 갱신된다.

이 다음으로 만들어진 20을 가지고 진행하는 것이 아닌 기존 카드 묶음에서 다시 최소 묶음인 10과 10을 골라야 하는 것이다.

문제를 푼 지금은 왜 이걸로 해맸는지 이해가 안 가기도 하지만 문제를 풀 당시에는 이거로 시간을 많이 잡아먹었다 😥

이 부분만 조심하면 우선순위 큐로 쉽게 해결할 수 있다.

1. 우선순위 큐를 선언한다.
2. 각 단계마다 최소값 2개를 뽑고 그 2개를 더한 값을 result에 더한다.
3. 이후 그 2개의 값을 더한 값도 다시 우선순위 큐에 삽입한다.

우선순위 큐는 기본적으로 내림차순 정렬이 되어, top의 값이 최대값을 지니게 된다. 이 문제에서는 오름차순 우선순위 큐가 필요한데, 이를 선언하는 방법은 다음과 같다.

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

이렇게 우선순위 큐를 선언하면 top의 값이 최소값을 지니게 된다.

💻 Code

---

#include <iostream>
#include <queue>

using namespace std;

int main() {
	int N, paper;
	cin >> N;

	priority_queue<int, vector<int>, greater<int>> que;
	for (int count = 0; count < N; count++) {
		cin >> paper;
		que.push(paper);
	}

	// exception : N == 1
	if (N == 1) {
		cout << 0;
		return 0;
	}

	int result = 0;
	while (que.size() != 1) {
		int data_1 = que.top();
		que.pop();
		int data_2 = que.top();
		que.pop();

		result += (data_1 + data_2);


		que.push(data_1 + data_2);

	}

	cout << result << endl;


}

처음 봤을 때 골드 문제여서 쫄았던 것이 사소한 실수를 만든 것 같다. 😓

---

---

⚡개인적으로 공부하면서 포스팅한 글입니다. 오류가 있는 경우 지적해주시면 감사하겠습니다!⚡