[백준] 2109 : 순회공연 - Python

문제

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

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

내 코드

import heapq
import sys
from collections import deque

sys.stdin = open("input.txt", "rt")

# n<=10,000
# n개의 대학에서 강연요청.
# 각 대학에서 d일 안에 와서 강연하면 p만큼의 강연료 지불하겠다고 알려왔다.
# 각 대학에서 제시하는 d와 p값은 서로 다를 수 있음
# 가장 많은 돈을 벌 수 있도록 순회강연 진행.
# 하루에 최대 한 곳에서만 강연

n = int(input()) # n개의 대학
data = []
for _ in range(n):
    p,d = map(int, input().split()) # 각 대학이 d일안에 와서 강연하면 p만큼의 보수 준다
    data.append((d,p))

data.sort(key = lambda x : x[0], reverse = True) # 날짜 큰 순으로 내림차순 진행
print(data)
dq = deque(data)
# 앞에서부터 하나씩 확인하기 위해 덱을 활용.
heap = [] # 최대힙을 위한 리스트
res = 0
max_day = dq[0][0] # 가장 큰 날짜 기준으로 1일까지 낮춰가면서 확인해야 함.
idx = 0
for day in range(max_day, 0, -1):
    # while dq and dq[0][0] >= day:
    #     d,p = dq.popleft()
    #     heapq.heappush(heap, -p) # 내림차순
    while idx < n:
        if data[idx][0] >= day:
            heapq.heappush(heap, -data[idx][1])
            idx += 1
        else:
            break
    if heap: # 존재하면 더해주기 날짜별로 한개씩 가능하므로 max_day에서 하나씩 줄여나가면서 하는 것이 핵심이었음
        now = -heapq.heappop(heap)
        print(f"더한 놈 : {now}")
        res += now #
        print(f"현재까지 합산 : {res}")
print(res)

우선순위 큐를 쓰는 것은 맞다. 근데 내림차순 정렬을 통해 확인하기 떄문에 deque를 사용하거나 인덱스를 이동하면서 문제를 풀었으면 됐다.

코멘트

최대로 벌 수 있는 경우의 수를 체크하는 것으로, 그리디 알고리즘으로 풀이가 가능하다.
직관적으로 일단, 비용이 큰 순서대로 내림차순 정렬을 하면 좋겠다. 라는 생각을 할 수 있따.

현재 강의료 가장 비싼 것을 강연한다 -> 그리디.
d일 안에만 와서 하면 된다는게 중요 포인트
ex) 2일 안에 와서 강연 해달라 -> 1일에 해도 되고, 2일에 해도 되고.. 그렇다는 건 날짜를 주어진 강연들 중 마지막 날짜에서부터 줄어들면서 처리하는게 좋겠다. 왜냐하면 1일부터 하면 3일안에 해도 되는게 뽑힐 수도 있음.

결국 시간이 큰 값은 작은 시간 때도 할 수 있다는 것을 알고 접근했어야 함
입력된 값을 시간이 큰 값부터 우선순위 큐에 집어 넣고 다음 시간으로 넘어가기 전에 (현재 시간보다 작은 시간) 가장 큰 값을 선택.
그 다음 시간에서 우선순위 큐에 남아있는 값 중 가장 큰 값을 선택. 그 이전에 선택되지 않은 값이 크다면 선택 가능하도록.
마지막까지 반복하고 선택된 값의 합을 출력하면 됐다.

풀이의 핵심은
가장 늦은 날짜(max_day)부터 1일까지 반복문을 수행하면서 각 날짜에서 가능한 강연들을 deque에서 꺼내 최대 힙에 넣는다.
해당 날짜에서 가능한 최대 강연료를 꺼내 결과에 누적.

최종 코드

import heapq
import sys
from collections import deque

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

data.sort(key=lambda x: x[0], reverse=True)  # 날짜 큰 순으로 내림차순 정렬
dq = deque(data)  # 덱 활용
heap = []  # 최대 힙
res = 0
max_day = dq[0][0]  # 가장 큰 날짜

for day in range(max_day, 0, -1):
    while dq and dq[0][0] >= day:
        d, p = dq.popleft()
        heapq.heappush(heap, -p)  # 최대 힙을 위해 음수로 저장
    if heap:  # 해당 날짜에 강연 가능하면
        now = -heapq.heappop(heap)  # 최대 강연료 꺼내기
        res += now  # 결과에 누적

print(res)

그리디 + 우선순위 큐 -> 연료 채우기 문제도 함께 풀면서 이런 유형의 문제가 나왔을 때 어떻게 풀어야 할 지 기억하자.

또한 백준 [컵라면] 역시 또 풀어보자.

[보석도둑] 문제 역시 같은 유형

[과제] 문제도 그리디 + 우선순위 큐 문제