[백준-파이썬] 2109: 순회강연

문제 보러 가기!

풀이 🎊

• 모든 강연 요청을 (요금, 일자) 형식의 tuple로 이뤄진 리스트에 저장했다.
• 일자 -> 요금이 큰 순서대로 정렬했다.
• d일 안에 강연을 해야 한다는 것에 대해 생각해보자. d가 7이라면, 1일 안에 강연해도 되고 2일 안에 해도 되고 3일 안에 해도 되고 .... 7일 안에 강연해도 된다는 뜻이다. 만약 d가 1이라면 1일 안에 강연해야만 돈을 준다는 뜻이다. => 일자가 큰 순서대로 봐준다!!
  • 일자가 큰 순서대로, 그 일자에 가능한 강연의 비용을 우선순위 큐에 넣는다. (같은 d로 요청한 강연이 여러 개라면 모두 넣는다)
  • 그 후 각 일자마다 보면서, 그 일자에 강연을 한다고 했을 때 돈을 가장 많이 주는 강연을 한다. (우선순위 큐에서 heappop)

주의점 👻

• heapq는 최소 우선 순위 큐인데, 지금은 최댓값이 필요하다. 그러므로 -1을 곱해서 큐에 넣고, pop해서 사용할 때도 -1을 곱해서 사용한다.

헷갈렸던 점 🐸

• for문 나온 후에, 남은 날들 각각 일자에 돈 가장 많이 주는 순회 강연을 해야 하는데(=남은 일자만큼 heapq.heappop()을 하면 됨) 그 부분을 빠뜨렸다.
• for 문 안 else 부분에서, 그 이전 일자들 각각을 봐줘야 하는데 처음에는 하루만 봐서 틀렸다.

코드 👩‍💻

import sys, heapq

input = sys.stdin.readline

N = int(input())
if N == 0:
    print(0)
else:
    lecture_requests = list(tuple(map(int, input().split())) for _ in range(N))
    # 일자, 요금 큰 순서대로 정렬
    lecture_requests.sort(reverse=True, key=lambda x: (x[1], x[0]))

    can_go_lectures = []
    ans = 0  # 최대 벌 수 있는 돈
    which_day = lecture_requests[0][1]  # 최대 일자

    for i in range(N):
        price, day = lecture_requests[i]
        if which_day == day:
            heapq.heappush(can_go_lectures, -1 * price)

        else:
            # 그 이전 날짜들 각각 -> 강연해서 벌 수 있는 돈 중에 젤 많이 주는 곳으로 가기!
            days = which_day - day
            while can_go_lectures and days:
                max_price = -1 * heapq.heappop(can_go_lectures)
                ans += max_price
                days -= 1

            which_day = day
            heapq.heappush(can_go_lectures, -1 * price)

    # 남은 날에 순회 강연하기
    for i in range(which_day, 0, -1):
        max_price = -1 * heapq.heappop(can_go_lectures)
        ans += max_price

    print(ans)