[백준 BOJ 1715 gold4 - 카드 정렬하기] priority queue(힙, 우선순위 큐 ) , c++

 

백준 1715 카드 정렬하기

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

1715번: 카드 정렬하기

 

카드 묶음 A와 B를 묶기 위해서는 A+B만큼의 비교가 필요하다. 

여러 묶음이 있을 때 다 하나의 묶음으로 만들기 위해 필요한 '최소' 비교 회수를 구해야 한다.

 

작은 것부터 묶었을 때가 최소가 되는 것을 예제를 보면 쉽게 알 수 있다. 

priority queue를 사용해서 작은 것부터 묶고, 묶고난 것을 다시 queue에 넣어주면서 반복한다.

 

처음에 queue에 다 넣고 단순히 앞에서부터 묶는 걸로 풀었는데 틀렸습니다가 떴다.

-> 앞의 두개를 묶고 이 묶은 것을 다시 queue에 넣어줘야 한다. 

 

예를 들어 1 2 3 4 5 6 이 있을 때

틀린 방법 ) 그냥 앞에서부터 1+2 / 3+3 / 6+4 ...

1 2 3 까지 묶었을 때의 크기는 6이고, 이때 묶음의 종류는 4 5 6 6 이 된다. 그러므로 6+4 가 아니라 작은 두수 4+5 를 해줘야 한다.

 

while (!pq.empty()) {
		int first = -pq.top();
		pq.pop();
		int second = -pq.top();
		pq.pop();

		total += (first + second);

		if (pq.empty()) break;
		
		pq.push(-(first + second));
	}