[백준-14501] 퇴사 👀

❓ Problem

🤔 How

1. 역순으로 dp테이블을 구성한다.
   • 첫날부터 탐색할경우 일하는경우 하지않는경우 모두 탐색하기에 dp테이블로 일반화하기에는 어려움이있다. dp[i] 는 i 일부터의 최대값 으로 dp테이블을 만들어준다.
2. dp 테이블의 갱신
   • 테이블은 다음과같이 갱신된다

일을할수 있는경우

• dp[i] =max(dp[i+d]+v,dp[i+1]) dp[i+d]+v 오늘일할경우 오늘일의 가치와 오늘일이 끝난이후의 최대값과 더해준 결과가 dp[i+1] 다음날 최대값과 비교해서 최대값을 갱신해준다.

일을 할수없는경우 다음날의 최대값 과 같다.

• dp[i]=dp[i+1]

❗ Solve

#퇴사
import sys
input = sys.stdin.readline

if __name__ == "__main__":

    work_list=[]
    for _ in range(n:=int(input())):
        work_list.append(tuple(map(int,input().split())))
    dp=[0]*(n+1)
    for i in range(n-1,-1,-1):
        d,v=work_list[i] # d 수행일수, v 가치
        if d+i<=n: # dp 의 인덱스를 넘으면안됨 
            dp[i]=max(dp[i+d]+v,dp[i+1]) # i의최대값은 n-1 부터시작 이전까지의 최대값이거나
            continue
        else:
            dp[i]=dp[i+1]
    print(dp[0])
    pass