[python] 백준 2109 순회강연

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

2109번: 순회강연

문제 해결

• 전형적인 그리디 문제
• 제안을 큰 p 순서, 작은 d 순서로 정렬을 시킨 다음 큰 p부터 최대한 늦게 스케줄이 비어 있는 날에 제안을 수락하려고 한다.
• 그러면 촉박한 d를 가진 것도 많이 할 수 있기 때문에 큰 값을 주는 순서대로 마감일자부터 가까운 날까지 확인하면서 계획이 없는 날에 강연을 하기로 하고 코드를 짜면 끝!

 

CODE

n = int(input())
dp = [0]*(10001)
memo = []
for _ in range(n):
    p, d = map(int, input().split())
    memo.append((p,d))
memo.sort(key= lambda x: (-x[0], x[1]))
for i in range(n):
    np, nd = memo[i][0], memo[i][1]
    for j in range(nd,0,-1):
        if dp[j] ==0:
            dp[j] = np
            break
print(sum(dp))