15486 퇴사 2

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

"""
일이 끝나야 요금을 받는다고 생각하자.
"""

import sys
read = sys.stdin.readline

N = int(read())
days = []
for day in range(N):
    days.append(list(map(int,read().split())))
d = [0 for _ in range(N+1)]
max_fees = 0
for i in range(N):
    now_t,now_p = days[i]
    max_fees = max(max_fees,d[i])
    if i + now_t <= N :
        d[i+now_t] = max(max_fees+now_p, d[i+now_t])
print(max(d))

3. 풀이 및 생각

문제 풀이

이 문제의 핵심은 하루하루 일을 체크하면서, 현재까지의 최대 일을 저장하는 것이다.

그래야 이런 문장이 성립하기 때문이다.

현재 내가 할 수 있는 일을 하면 $T_i$일 후에 새로운 일이 가능하므로 $i+T_i$에 해당하는 날짜에 $d[i+T_i]+P_i$를 할 수 있을 것이다. 그러나, 기존에 $d[i+T_i]$에는 다른 날로부터 시작된 요금의 합이 저장되어 있을 수 있으니, max()를 이용해서 값을 항상 갱신토록 한다.

나의 생각

이 문제는 몇번을 생각해도 금방 와닿지 않는 문제였으므로 다음에 꼭 다시보자.