백준 2109

처음에는 우선순위 큐를 사용해서 비용이 크고 기간이 짧은 강연을 먼저 고르면 될 줄 알았다.

그런데

4

5 1

10 2

20 2

10 3

이러한 예시가 들어올 경우

5 + 2 + 10 이 아니라

10 + 20 + 10 을 선택해야 했다.

왜냐하면 기간 내에 강연을 가는 것도 가능하기 때문이다.

 

그래서 아예 새로운 방법을 사용해야 했다.

1. 최대 기간 maxDate 잡기

2. 비용이 큰 순서대로 입력값 정렬하기

3. maxDate에서 하루씩 줄여가며 가능한 강연 찾기

 

위 예시에서는 maxDate = 3 이 될 것이다.

비용이 큰 순서대로 입력값을 정렬하면

[[20, 2], [10, 2], [10, 3], [5, 1]] 이 될 것이다.

그러면 3에서 부터 2, 1 와 같이 1씩 줄여가면서 해당 날짜에 가능한 강연을 검사하고, 

10 + 20 + 10 = 40 이 결과값이 된다.

 

 

예시 코드

import sys

N = int(sys.stdin.readline())
if(N == 0):
    print(0)
else:
    data = []
    for i in range(N):
        p, d = map(int, sys.stdin.readline().split())
        data.append([-p, d, True])

    data.sort(key=lambda x : x[1], reverse=True)
    maxDate = data[0][1]
    data.sort(key=lambda x : (x[0], x[1]))

    # 가능한 강연 검사
    sum = 0
    while(maxDate > 0):
        for i in range(N):
            if(data[i][1] >= maxDate and data[i][2]):
                sum -= data[i][0]
                data[i][2] = False
                break
        maxDate -= 1

    print(sum)