[백준] 순회강연(2109) - python

✏️ 문제

한 저명한 학자에게 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만큼의 돈을 벌 수 있다.

🎈 입력

첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.

🎈 출력

첫째 줄에 최대로 벌 수 있는 돈을 출력한다.

🎈 입출력 예

<입력>
7
20 1
2 1
10 3
100 2
8 2
5 20
50 10

<출력>
185

👩‍💻 내 코드

처음에 문제를 풀 땐 단순하게 생각하고 풀어서 굉장히 쉽다고 생각했다. 나와있는 테스트 케이스만 따지면 각 일 마다 높은 강연료를 주는 학교를 선택해도 정답이 나온다. 이렇게 단순히 생각해서 아래와 같이 코드를 짰고 역시나 9%때 바로 틀리고 말았다.

n = int(input())

school = {}

for _ in range(n):
    tmp = list(map(int, input().split()))

    if tmp[1] not in school:
        school[tmp[1]] = [tmp[0]]
    else:
        school[tmp[1]].append(tmp[0])

school = dict(sorted(school.items()))

for k, v in school.items():
    school[k] = sorted(v, reverse=True)

result = 0
for v in school.values():
    result += v[0]

print(result)

왜 틀렸는지 고민한 결과 아래와 같은 경우를 처리하지 않았다는 것을 알게되었다.

<입력>
7
20 1
2 1
10 3
100 2
200 2
5 20
50 10

<출력>
365

때문에 다음과 같이 아이디어를 구상하여 코드를 구현했다.

1. 딕셔너리를 이용해 데이터 매핑
   key: 일 수, value: 강연료
2. 딕셔너리 key를 중심으로 정렬
3. 일 수가 작은 것 부터 차례대로 힙에 넣고 최소힙을 이용해 일 수에 맞춰 강연료가 가장 작은 것을 제거

import heapq
n = int(input())

school = {} 

# 1. 딕셔너리를 이용해 데이터 매핑
# key: 일 수, value: 강연료
for _ in range(n):
    tmp = list(map(int, input().split()))

    if tmp[1] not in school:
        school[tmp[1]] = [tmp[0]]
    else:
        school[tmp[1]].append(tmp[0])

# 딕셔너리 key를 중심으로 정렬
school = dict(sorted(school.items()))

# 최소힙을 이용해 일 수에 맞춰 강연료가 가장 작은 것을 제거
total_p = []
for k, v in school.items():
    for i in range(len(v)):
        heapq.heappush(total_p, v[i])

    while len(total_p) > k:
        heapq.heappop(total_p)

print(sum(total_p))

어디가 잘못되었는지 문제의 원인을 찾고 스스로 해결해서 문제를 풀며 굉장히 뿌듯했다.ㅎㅎ 이 맛에 알고리즘 문제를 푸는 것 같다!