(cpp) Baekjoon 1715번 문제 ‘카드 정렬하기’ - 자료구조, 그리디 알고리즘, 우선순위 큐

on Programming Languages

Baekjoon 1715번 문제 ‘카드 정렬하기’ - 자료구조, 그리디 알고리즘, 우선순위 큐

문제

문제풀이

(A+B) + (A+B+C) + (A+B+C+D) + …로 생각하여 가장 작은 숫자가 가장 많이 더해지도록 구현할 수 있지만 이는 틀린 방법이다. 예를 들어 5 6 7 8의 경우, 위와 같은 방식으로 해를 구하면 55가 나오지만 실제 답은 52이다. (5+6)+(7+8)+(11+15)=11+15+26=52로 계산된다.
우선순위 큐를 하나 만들고 입력값들을 큐에 집어넣되, 가장 작은 두 개의 값은 서로 더한 후에 집어넣는다. 예를 들어, s=[5 6 7 8]이면, q=[11 7 8]이 되는 것. 이 상태에서 한번 더 정렬해서 가장 작은 두 수 를 찾고 서로 더한 후에 집어 넣는 것을 반복한다. q=[11 15]가 되며 이 과정에서 answer에 더해진 결과물을 저장해두었다가 계속해서 갱신한다. 즉, answer = (5+6) + (7+8) + (11+15) = 52가 된다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<queue>
#include<functional>
using namespace std;

int n, num,n1,n2;
int answer = 0;
priority_queue<int,vector<int>,greater<int>> q; 

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num;
		q.push(num); 
	}
	while (q.size()!=1) {
		n1 = q.top(); 
		q.pop(); 
		n2 = q.top(); 
		q.pop();  
		q.push((n1+n2)); 
		answer = answer + (n1 + n2); 
	}
	cout << answer;
}
  • 단지 순차적으로 계산하면 안되고, 카드 뭉치 합칠 때마다 합칠 카드 뭉치 후보를 갱신해주어야 함.
  • 우선순위 큐는 기본적으로 내림차순 정렬되므로 오름차순 정렬을 위해 greater옵션다추가한다.
  • 큐에서 top은 우선 순위 가장 높아서 맨 앞에 있는 숫자이고, pop()하면 그 숫자가 빠지는 것(스택하고 구조 다르다)