[백준 - Python] 2109 - 순회강연

0.  문제 링크

 

 

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

2109번: 순회강연

---

1.  풀이 방법

 

1. 맨 처음 페이를 기준으로 정렬하고, 페이에 따른 기한 날짜에 넣는다.
2. 만약 이미 그 기한 날짜에 다른 강의가 있다면 시간을 하루씩 당겨서 넣을 수 있는지 체크한다.
3. 추가로 go to this day를 만들어서, 특정 기한 날짜의 강의는 this day의 날짜부터 강의를 할 수 있다고 정의한다.
4. 또한 capacity를 만들어서, capacity의 날짜까지는 모든 강의가 차있으므로, 어떤 날짜가 capacity 아래라면 강의할 수 없다.

---

2.  코드

 

 

import sys
import heapq
input = sys.stdin.readline


if __name__ == "__main__":
    n = int(input())
    maps = []
    go_to_this_day = dict()

    for _ in range(n):
        pay, day = map(int, input().split())
        go_to_this_day[day] = day
        heapq.heappush(maps, (-pay, day))

    check = set()       # 어느 날짜들을 넣었는지
    ans = 0
    capacity = 0        # 어느 날짜까지는 꽉 차있음

    while maps:
        pay, day = heapq.heappop(maps)
        day_ori = day       # 추후 원래 값을 이용해야 함
        day = go_to_this_day[day]     # 특정 날짜까지 갈 수 있는 강연은 이 날짜 아래로 갈 수 있음

        if day <= capacity: continue     # 특정 날짜까지 꽉 차있는데, 그것보다 작으면 못감

        while day > 0 and day in check:     # 날짜가 1보다 커야하고, 예약이 없어야 함, go_to_this_day에서 체크해도, 다른 날짜가 기한인 강의가 이미 예약했을 수도 있으므로
            day -= 1
        if day:     # 0이 아니면 예약
            check.add(day)
            ans -= pay
            go_to_this_day[day_ori] -= 1        # 특정 날짜까지 갈 수 있는 강연 날짜는 현재 값 - 1을 해야함
        else:
            capacity = day_ori      # 한계값
            go_to_this_day[day_ori] = 0     # 특정 날짜까지 할 수 있는 강의는 이제 없음

    print(ans)

---

3.  마무리