백준 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를 사용한다는 것을 처음 알게 되었습니다.
그리고 실제 구현은 우선순위큐를 이용한 것과, 이분탐색을 이용한 방법 두 가지로 해결했는데, 코드 링크는 이분탐색을 구현한 코드입니다.
What's the difference between heapq and PriorityQueue in python?
In python there's a built-in heapq algorithm that gives you push, pop, nlargest, nsmallest... etc that you can apply to lists. However, there's also the queue.PriorityQueue class that seems to supp...
stackoverflow.com
문제 링크 : https://www.acmicpc.net/problem/1715
1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장
www.acmicpc.net
코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/1715.py