[백준/1715] 카드 정렬하기

출처: 1715번: 카드 정렬하기 (acmicpc.net)

1715번: 카드 정렬하기

 

 전형적인 그리디 유형의 문제입니다. 대략적인 점화식을 써보자면 sum_n = a_n + sum_n-1과 같습니다. 즉 이전까지의 카드 뭉치의 합은 계속 더해지므로 가장 작은 카드 뭉치들을 먼저 합쳐나가는 방식으로 풀어나가면 됩니다.

 다만 주의할 점은 단순한 정렬과 반복으로는 풀 수 없다는 점입니다. 다음 코드를 살펴봅시다.

 

n = int(input())
array = []
for _ in range(n):
    array.append(int(input()))
    
array.sort()

prev = array[0] + array[1]
for i in range(2, n):
    prev = 2 * prev + array[i]

print(prev)

 가장 처음 접근한 아이디어입니다. 리스트의 원소를 정렬시킨 뒤, 앞에서부터 차례로 더해나갑니다. 10, 20, 40의 3개의 원소가 있다고 가정할 경우, (10+20) + (30+40)과 같이 계산되므로 이는 (10+20) + (10+20) + 40이며, 간단히 2 * (10 + 20) + 40으로 치환할 수 있습니다. 이를 적용하여 코드를 작성한 모습입니다.

 

 단 이러한 접근법에는 치명적인 오류가 존재합니다. 만약 10, 20, 40, 50, 60의 원소가 존재한다고 가정할 경우, 처음엔 10과 20이 합쳐질 것입니다. 이 때 리스트에는 30, 40, 50, 60이 존재합니다. 이후에는 30과 40이 합쳐질 것입니다. 이렇게 되면 리스트에는 70, 50, 60이 존재합니다. 여기서 문제가 발생합니다. 만약 순서대로만 계산이 진행되는 것이라면 70과 50이 합쳐질 것입니다. 그러나 실제로 현재 리스트에서 가장 작은 원소는 50과 60입니다. 따라서 단순한 반복으로는 적절한 원소를 선택할 수 없다는 것이 증명됩니다.

 

---

 각 경우에 대해서 가장 작은 원소 두개를 뽑아내기 위해서 heapq 라이브러리를 이용하면 편리합다. heapq를 이용한 실제 정답 코드는 다음과 같다.

import heapq

n = int(input())
q = []
for _ in range(n):
    heapq.heappush(q, int(input()))

cnt = 0
while len(q) > 1:
    v = 0
    for _ in range(2):
        v += heapq.heappop(q)
    cnt += v
    heapq.heappush(q, v)
    
print(cnt)

 모든 원소를 애초에 우선순위 큐에 받아서 정렬시킵니다. heapq는 최소 큐를 지원하기 때문에 자연스럽게 카드가 적은 순서대로 정렬되게 됩니다. 이후 q의 원소가 한 개가 될때까지 가장 작은 원소를 두 개씩 뽑아가면서 cnt 변수에 더해 나갑니다. 더해진 값은 다시 사용될 수 있도록 우선순위 큐에 삽입합니다.

 

정리

여담으로 처음에는 DP를 이용해서도 접근해보았는데, 메모리 초과 판정을 받아 이것 저것 해보았습니다. 삽질을 좀 하다보니 Pypy3가 속도에 이점은 있지만, 메모리 관리 면에서 python3에 비해 조금 더 비효율적이라는 것도 알게 되었습니다. 전문가는 어떤 분야에서 할 수 있는 실수를 다 해본 사람이라는 말이 다시금 떠오르네요.

 어쨌든 여러모로 heapq 라이브러리는 편리하게 사용되는 것 같으니 꼭 사용법을 익혀두는 편이 좋은 듯 합니다.