백준 1715번 카드 정렬하기

문제 설명

A(10개)와 B(20개) 숫자 카드 묶음을 합치려면 각 묶음의 카드 개수를 더한 만큼의 비교횟수가 필요할 때, 여러 카드 묶음을 한 개로 합치려면 최소한 몇 번의 비교가 필요한지 구하는 문제입니다.

 

문제 풀이

아이디어

최소 비용으로 합치는 방법

10,20,40개의 숫자 묶음이 있을 경우를 생각해보도록 하겠습니다.

 

10,20을 먼저 합치고 40을 합칠 경우

10+20, 30+40 -> 총 30 + 70 = 100의 비용이 필요합니다.

 

10,40을 먼저 합치고 20을 합칠 경우

10+40, 50+20 -> 총 50 + 70 = 120의 비용이 필요합니다.

 

20, 40을 먼저 합치고 10을 합칠 경우

20+40, 60+10 -> 총 60 + 70 = 130의 비용이 필요합니다.

 

그렇다면 10,20을 먼저 합치고 40을 합칠 경우가 최소 비용으로 합칠 수 있는 경우가 됩니다.

 

이유

10,20을 먼저 합치고 40을 먼저 합칠 경우, 첫번째로 묶은 숫자 묶음 비교 비용 30을 한 번 더 40에 더하게 됩니다.

이것을 식으로 표현하면, 10 + 20 + (10+20) + 40이 되는 것입니다.

위의 식을 보면 각 숫자 묶음의 카드 개수를 무조건 한 번 씩은 다 더하고, 괄호로 친 부분(이 전의 숫자 묶음 비교 비용)이 한 번 더 더해지는 것을 볼 수 있습니다.

그러므로, 숫자 묶음의 비교 비용을 최소로 하려면 이 한 번 더 더해지는 것을 최소로 하면 됩니다.

즉, 합치는 카드 묶음의 비교를 최소로 하기 위해, 항상 가장 적은 장 수를 가진 숫자 묶음을 합치면 됩니다.

 

항상 가장 작은 수를 더하는 방법

현재 합치려는 카드 묶음 중 가장 적은 장 수의 카드 묶음 2개를 뽑아야 최소 비교 비용을 구할 수 있습니다.

그러므로, 카드를 합친 후 합친 카드 묶음을 원래 있던 카드 묶음에 다시 넣었을 때 정렬된 상태를 유지해야 합니다.

 

풀이

우선순위큐

파이썬의 내장함수 heapq나 priorityqueue를 이용해 항상 가장 작은 두 묶음을 비교할 수 있도록 해줍니다.

우선순위큐의 원소 개수가 1개가 될 때까지 반복문을 돌면서, 가장 작은 원소 두개를 빼서 더해주고 다시 우선순위에 넣어주면 우선순위 큐에 마지막으로 남이있는 원소가 답이 됩니다.

 

 

해결

파이썬의 우선순위큐에 대해 찾는 도중 priorityqueue와 heapq를 찾았는데, priorityqueue의 구현 내용이 heapq를 사용한다는 것을 처음 알게 되었습니다.

그리고 실제 구현은 우선순위큐를 이용한 것과, 이분탐색을 이용한 방법 두 가지로 해결했는데, 코드 링크는 이분탐색을 구현한 코드입니다.

https://stackoverflow.com/questions/36991716/whats-the-difference-between-heapq-and-priorityqueue-in-python

What's the difference between heapq and PriorityQueue in python?

문제 링크 : https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/1715.py