BOJ 백준온라인져지 1715 카드 정렬하기 풀이

이제 heap 을 직접 구현하지 않고, priority queue 를 사용한다.

그리고 이 문제를 푸는데 계속 틀렸다.

틀린 이유는 card 의 조합 개수가 1일 때 0을 출력해야 되는데,

입력 된 카드를 다 출력해서 계속 100%에서 틀렸다.

수식은 

a + b + ((a + b) + c)

위에 단계가 반복되면 결과가 나온다.

(a + b) = result 에 계속 더해주면 된다.

증명은 아직 할줄을 몰라서..

	#include <cstdio>
	#include <queue>
	/**
	* https://www.acmicpc.net/problem/1715
	* BOJ 백준온라인져지 1715 카드 정렬하기 풀이
	*/
	using namespace std;
	int main () {
	int cardCount;
	scanf("%d", &cardCount);
	priority_queue<int, vector<int>, greater<int> > queue;
	while (cardCount--) {
	int temp;
	scanf("%d", &temp);
	queue.push(temp);
	}
	int result = 0;
	while (queue.size() > 1) {
	// a + b + ((a + b) + c)
	// result = (a + b)
	int a = queue.top(); queue.pop();
	int b = queue.top(); queue.pop();
	result += a + b;
	queue.push(a + b);
	}
	printf("%d", result);
	}

view raw BOJ_1715.cpp hosted with ❤ by GitHub