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

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

언어: C++, 시간: 36ms

 

접근방법

정렬을 계속 반복하는 그리디 문제!

가장 작은 숫자가 top에 오는 pq를 만들고 난 후,

숫자들 중 가장 작은 숫자와 그 다음 숫자를 더하고, 이걸 정답 변수에 더해주고 난 후 다시 pq에 넣는다. ....

→  이걸 pq 크기가 1이 될 때까지 반복하기

 

고려사항

이 문제는 모두 int로 풀이해도 된다.

문제에서 N은 10만, 카드묶음의 최대 숫자는 1000인데,

정답 변수에는 1000x10만 + 2000x5만 + 4000x2만5천 + 8000x만2500, ... 이런식으로 1억이 계속 더해진다.

이 때 log100000 = 16.609... 이므로, 1억이 16.609... 번 더해지는 셈이다.

약 16.6억 < 21억이므로 , int로도 충분하다😎

 

최종코드

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

int N, temp, answer;
priority_queue <int, vector<int>, greater<>> pq;

int main() {

	cin >> N;
	for (int i = 0; i < N; i++){
		cin >> temp;
		pq.push(temp);
	}

	while (1) {
		if (pq.size() == 1)
			break;

		int lessFirst = pq.top();
		pq.pop();
		int lessSecond = pq.top();
		pq.pop();
		int newNum = lessFirst + lessSecond;
		answer += newNum;
		pq.push(newNum);
	}

	cout << answer;

	return 0;
}