[백준] 14501번 - 퇴사 (파이썬)

https://www.acmicpc.net/problem/14501

# 퇴사

N = int(input())
arr = []
for _ in range(N):
    day, pay = map(int, input().split())
    arr.append((day, pay))
dp = [0] * (N+1)

for i in range(N-1, -1, -1):
    day = arr[i][0]
    pay = arr[i][1]
    if day + i <= N:
        dp[i] = max(pay + dp[day+i], dp[i+1])
    else:
        dp[i] = dp[i+1]

print(dp[0])

 

DP

1. arr에 걸리는시간(day), 금액(pay)를 순서대로 append

2. dp는 N+1로 선언

3. 뒤에서부터 if(현재 위치 + day <= 퇴사일 까지의 날)이면

   - 전날 까지 했던 총 받을 금액(dp[i+1])과 현재 시점부터 일이 걸리는시간(day) 이후의 총 받을 금액(dp[day+i])

      + 일완료시 받을 금액(pay)를 비교해서 더 큰 값을 현재시점에서 받을 총 금액(dp[i])으로 초기화

4. 아니면 dp[i]를 전날의 총 받을 금액(dp[i+1])로 초기화

5. dp[0] 출력

 

역시 나는 dp가 가장 약한 것 같다