[BOJ] 1715 카드 정렬하기

우선순위 큐 문제를 별로 안풀어봐서인지, 혼자서는 솔직히 이 문제가 우선순위 큐인지 알아차리지 못했을 것 같습니다...

가장 중요한 것은 적어도 배열의 맨 앞의 값 두개는 항상 가장 작은 값이여야 할 것이라고 생각했고, 우선순위 큐를 이용해서 풀어주었습니다.

파이썬으로 작성한 코드

우선순위 큐에 집어 넣고 매번 pop을 통해 2개의 값을 꺼낸뒤 합을 total에 더하고 다시 큐에 넣어줬습니다. 그렇게 반복할 때 마다 큐의 길이가 1씩 줄어들게 되는데 queue의 길이가 1이면 반복문을 탈출시켜줄 수도 있지만 매번 비교를 해야되므로 if를 쓰거나 while에 조건을 다는 대신 try와 except로 빈 큐에 pop을 하려 했을 때 나는 에러를 이용해서 탈출시켜 주었습니다.

import sys
import heapq
input=sys.stdin.readline

n=int(input())

pq=[]
total=0

for i in range(n):
	heapq.heappush(pq,int(input()))

while True:
	try:
		n1=heapq.heappop(pq)
		n2=heapq.heappop(pq)
		total+=n1+n2
		heapq.heappush(pq,n1+n2)
	except: 
		break
	
print(total)

C++로 작성한 코드

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

int main()
{
    int n,num,n1,n2,len;
    int total=0;
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    priority_queue<int> pq;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>num;
        pq.push(-1*num);
    }
    
    while (1)
    {
        n1=pq.top();
        pq.pop();
        if (pq.empty()==1)
        {
            break;
        }
        n2=pq.top();
        pq.pop();
        total-=(n1+n2);
        pq.push(n1+n2);
    }

    cout<<total<<endl;
    
    return 0;
}

배열의 크기를 입력받아 그만큼 우선순위 큐에 넣어준 뒤 앞에서 숫자 2개를 빼고 그 합을 결과에 더해준뒤 다시 우선순위 큐에 푸쉬해주었습니다. 이것을 첫 번째 숫자를 뺐을 때 배열이 비어있을 때까지 반복시켜주고 그렇게 얻은 결과를 출력해주었습니다.

queue에 priority_queue가 있다는 것만 알고 만들었더니 큰수가 앞에 오도록 되어있어서 앞에 -를 붙여서 뒤집어주고 결과에 더할때 -를 붙여 활용했습니다. 파이썬의 pop()이랑 다르게 맨앞에 것을 가져가는 것을 몰라서 해맸네요..