<정렬> 2109번 순회강연 with 파이썬

 

문제

 한 저명한 학자에게 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값이 주어진다.

출력

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

정답비율

34.848%

알고리즘 분류

#자료구조 #그리디알고리즘 #정렬 #우선순위큐

 

import sys
import heapq
input = sys.stdin.readline

answer = []
n = int(input())
lst = []
for _ in range(n):
    p, d = map(int, input().split())
    lst.append((p,d))

lst.sort(key=lambda x:(x[1],-x[0]))
day = 1
for i in range(n):
    if lst[i][1] >= day:
        day += 1
        heapq.heappush(answer, lst[i][0])
    else :
        if lst[i][0] > answer[0] :
            heapq.heappop(answer)
            heapq.heappush(answer, lst[i][0])

print(sum(answer))

 

 - 두 번이나 틀린 문제이다. 처음에는 문제 이해를 잘못하였다. d의 의미를 d라는 일자에 강연을 해야한다고 착각했다. 그래서 d에 대해서 먼저 정렬하고 그 안에서 -x[0]에 대해 정렬한 후 (여기까지는 위의 코드와 동일) 단순히 각 일자에 대해 최댓값을 더했다. 이렇게만해도 예제 케이스는 통과한다.

 

 - 그러나 틀렸습니다 를 보고 다시 문제를 보니 d라는 날짜 "안에" 강연을 하면 된다는 것이다. 즉 10이라면 10일 안에 어느 날짜든 상관없다는 의미이다. 이 시점의 나의 테스트 케이스는 다음과 같다.

 

5
10 1
20 3
30 3
40 5
50 5
me : 90
answer : 150

 

 - 이번에는 day라는 1씩 커지는 임의의 변수를 이용하여 이보다 큰 d를 갖고있으면 answer에 더해주도록 하였다. 그렇게 했더니 위의 테스트케이스는 올바르게 나왔다. 그러나 또 다시 '틀렸습니다'를 마주했다.

 

 - 위에서 생각지 못한 케이스가 있는데 이는 다음과 같다.

 

3
1 1
10 2
10 2
me : 11
answer : 20

 

 - 그렇다 1일째에 1짜리를 하는 것보다 10짜리를 해버려야한다. 이 때 떠오른 것은 우선순위 큐이다. 원래 했던대로 day가 1씩 커지며 리스트에 담되, day보다 크지 않은 d가 나타나면 우선순위 큐의 가장 앞(가장 작은값)과 비교하고 이보다 크다면 pop시킨후 이번 차례의 값을 넣었다.

 

 

---

 

 

참고

 

2109번: 순회강연