* 백준 2109번 - 순회강연

Gyuhan Park·2021년 12월 22일
0

코딩테스트 정복

목록 보기
39/47

한 저명한 학자에게 n개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d일 안에 와서 강연을 해 주면 p만큼의 강연료를 지불하겠다고 알려왔다. 강연료의 최댓값을 구하시오.

# 정답 코드

전에 풀었던 과제문제랑 비슷한 맥락의 문제였다. 몇 일안에 해결하면 득점. 강연료의 최댓값이 중요하기 때문에 강연료의 내림차순으로 정렬하였고 이건 사실 적으면서 안건데 이 알고리즘에선 마감일은 별로 중요하지 않은 것 같다.

큰 강연료부터 마감일근처에 채운다. 그 뜻은 최대한 미뤘다가 한다는 소리고 그 전 마감일의 스케줄이 꽉찼다면 그 때 하는 강의의 강연료가 더 비싸다는 소리다.

그래서 결론적으로 스케줄을 꽉 채우면서 최대한 많이 받을 수 있다.

import sys

input = sys.stdin.readline

n = int(input())
schedules = [0] * 10001
lectures = []
for _ in range(n):
    pay, day = map(int, input().split())
    lectures.append((pay, day))

lectures.sort(key=lambda x: (-x[0]))

for i in range(n):
  for j in range(lectures[i][1], 0, -1):
    if schedules[j] == 0:
      schedules[j] += lectures[i][0]
      break

print(sum(schedules))

# 참고 코드

비슷한 문제인데도 불구하고 글을 쓴 이유는 난이도가 올라갈수록 heapq를 많이 사용하는 걸 느끼기 때문이다. 우선순위큐와 그리디 알고리즘을 섞어 문제를 많이 출제하는 것 같다.

이중 for문을 도는 리스트로 문제를 풀었을 때 맞은 이유는 속도제한이 여유있기 때문일거고, 여기서 핵심은 heapq로 푼 경우 속도가 9배나 빠르다.

이 코드는 오히려 마감일 기준 오름차순으로 정렬한다.
이유는 강연료는 heap이 알아서 정렬해줄거고 촉박한 강연부터 넣어야 len(p_list)와 비교가 가능하다.
그 후 순서대로 heapq에 넣는다.
넣은 점수가 갖고 있는 마감일과 p_list의 길이를 비교하는데, len(p_list) > i[1] 의 경우는 스케줄이 첫날부터 i[1]까지 꽉차있다는 뜻이다. 그럼 하나를 비워야 되는데 그때 heappop()을 하게 되면 강연료가 최소인 강연이 pop되기 때문에 p_list는 최대 강연료를 항상 가지고 있다는 걸 알 수 있다.

import heapq

n = int(input())
lst = []
for i in range(n):
    lst.append(list(map(int, input().split())))

lst.sort(key=lambda x: (x[1]))
p_list = []

for i in lst:
    heapq.heappush(p_list, i[0])
    if (len(p_list) > i[1]):
        heapq.heappop(p_list)

print(sum(p_list))
profile
단단한 프론트엔드 개발자가 되고 싶은

0개의 댓글