백준 13904번 : 과제 (Python)

출처 : https://www.acmicpc.net/problem/13904

n = int(input())
hw = []
max_d = 0
for _ in range(n) :
    d, w = map(int, input().split())
    hw.append((w, d))
    max_d = max(max_d, d)
hw.sort()

arr = [0] * (max_d + 1)
answer = 0
while hw :
    w, d = hw.pop()
    for i in range(d, 0, -1) :
        if arr[i] == 0 :
            arr[i] = w
            answer += w
            break

print(answer)

두 가지 풀이가 있다.

먼저 남은 일수와 점수를 입력 받아 hw에 저장하고, 점수가 낮은 순으로 정렬한다.

또한 입력 과정에서 가장 큰 남은 일수를 체크해 max_d에 저장한다.

그리고 과제가 제출된 날짜를 기록할, 길이가 max_d + 1인 배열 arr을 초기화한다.

다음으로 점수가 큰 과제부터, 즉 hw 배열의 뒤에서부터 순서대로 가능한 늦게(마감일에 가깝게) 제출한다.

과제를 제출한 날짜를 arr에 체크하고, 이미 그 날짜에 다른 과제가 제출되었으면 하루씩 앞으로 가며 제출되지 않은 날짜를 찾는다.

 

import heapq

n = int(input())
hw = [tuple(map(int, input().split())) for _ in range(n)]
hw.sort()

w_q = []
for d, w in hw :
    if len(w_q) < d :
        heapq.heappush(w_q, w)
    else :
        if w > w_q[0] :
            heapq.heappop(w_q)
            heapq.heappush(w_q, w)
            
print(sum(w_arr))

우선순위 큐를 활용하는 다른 풀이도 가능하다.

이번에는 hw 배열을 마감일이 빠른 순서로 정렬한다.

그리고 제출한 과제의 점수를 저장할 큐 w_q를 초기화한다.

hw 배열의 앞에서부터 하나씩 과제의 마감일 d와 점수 w를 확인한다.

현재 w_q 배열의 길이보다 d가 더 크면, 마감일이 겹치는 과제가 없으므로 그대로 제출할 수 있다.

따라서 해당 과제의 점수 w를 w_q에 넣어준다.

w_q 배열의 길이보다 d가 더 크지 않으면, 마감일이 겹치는 과제가 있다는 뜻이다.

이 경우에는 가장 점수가 낮은 과제, 즉 w_q의 첫번째 값과 w를 비교한다.

w가 w_q[0] 보다 더 클때 w_q[0] 대신 w를 제출하는게 더 이득이므로 heapop으로 w_q[0]을 빼주고 w를 추가한다.

 

이 문제는 백준 2109번 순회강연(https://www.acmicpc.net/problem/2109)과 완전히 동일한 문제이다.

다만 2109번 문제는 n과 d의 범위가 훨씬 크기 때문에 첫번째 방법의 풀이는 (통과는 되지만) 시간이 더 오래걸린다.