💡 문제
한 저명한 학자에게 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값이 주어진다.
출력
첫째 줄에 최대로 벌 수 있는 돈을 출력한다.
💭 접근
이 문제를 풀며 유의해야 할 점으론, 만약 입력이 (50, 2)으로 주어졌다면 이 강연은 반드시 이틀차에 진행하는 것이 아닌, 2일 이내에만 강연을 하러 가면 된다는 것이다. 따라서 위 강연은 1일차에 진행될 수도 있고, 2일차에 진행될 수도 있다는 것이다.
위 조건만 유념했다면 문제는 쉽게 해결할 수 있다.
-
먼저 전체 스케쥴을 저장할 리스트를 하나 생성한다. 이때 이 리스트의 인덱스는 강연을 진행할 날짜(
d)가 되고, 리스트에 저장되는 요소는 강연료(p)이다. -
우선 입력을 주어진 모든 강연을 강연료 기준 오름차순으로 정렬한다. (이렇게 되면 강연료가 가장 큰 강연이 뒤로 가게된다.)
-
이후, 강연료가 큰 순으로 가져오며 해당 날짜(
d)에 저장하는데 이 날짜를 기준으로 강연료가 현재 선택된 강연료보다 저렴한 강연을 만날때까지 탐색하고, 저렴한 강연을 만난다면 현재 선택된 강연으로 교체한다. -
마지막으로 모든 강연에 대해 탐색을 마쳤다면, 스케쥴에 저장되어 있는 모든 강연료를 더하여 출력한다.
📒 코드
import sys
# input = sys.stdin.readline
n = int(input())
courses = [list(map(int, input().split())) for _ in range(n)]
courses.sort(key=lambda x : x[0])
ans = [0 for _ in range(10001)]
while courses:
p, d = courses.pop()
for i in range(d, 0, -1):
if ans[i] < p:
ans[i] = p
break
print(sum(ans))💭 후기
오랜만에 쉽게 해결했던 그리디 문제라서 풀고 난 뒤에 뿌듯했다.
🔗 문제 출처
https://www.acmicpc.net/problem/2109
