백준 2109 파이썬 - 순회강연

https://www.acmicpc.net/problem/2109

2109번: 순회강연

문제

한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.

예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.

 

코드

import heapq
import sys

n = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
arr.sort(key=lambda x: x[1])
queue = []
for p, d in arr:
    heapq.heappush(queue, p)
    if d < len(queue):
        heapq.heappop(queue)
sys.stdout.write(str(sum(queue)))

풀이

파이썬에서 heapq는 가장 작은 값을 pop시켜준다는 것을 알고 활용해야 한다. 우선 입력 받은 값들을 d의 값으로 오름차순으로 정렬시켜주고, queue에 p를 넣어준 후에 해당하는 d가 queue의 길이보다 작은지 확인해 작은 값을 pop한다. if문의 조건으로 queue의 길이가 d보다 크다는 것은 날짜보다 강연 횟수가 더 크다는 것으로, 이럴 경우 가장 싼 강연을 하지 않도록 pop 하는 것이다.

 

오답

import sys
n = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
ans, check = [], []
for i in range(0, n - 1):
    for j in range(i + 1, n):
        if arr[i][1] == arr[j][1]:
            ans.append(arr[i][0] if arr[i][0] > arr[j][0] else arr[j][0])
            check.append(j)
            break
    else:
        if i not in check:
            ans.append(arr[i][0])
if n - 1 not in check:
    ans.append(arr[n - 1][0])
sys.stdout.write(str(sum(ans)))

heapq를 사용해야 한다는 것이 떠오르지 않았을 때의 풀이이다. 지금보니 뭔가 이상하게 푼 것 같다.