[백준/Python/DP] 퇴사

퇴사

나의 코드

최적화 실패
DP는 여전히 너무 어렵다 흑

import sys
input = sys.stdin.readline
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
print(arr)
dp = [0] * n
for i in range(n): # days 가 오래 걸리는거 0으로 만들기 
    days = arr[i][0]
    pay = arr[i][1]
    available = n - i
  
    if days > available:
        arr[i][0] = 0
        arr[i][1] =0
print(arr)


for i in range(n):
    days, pay = arr[i]
    print(days, pay)
    
    print(arr[i + days:])

정답 코드

bottom-up 방식

N = int(input())

t = []
p = []
dp = [0 for _ in range(N+1)]

for _ in range(N):
 T, P = map(int, input().split())
 t.append(T)
 p.append(P)

print(t)
print(p)
for i in range(N-1, -1, -1): # 뒤에서부터 거꾸로
 print(i)
 if t[i] + i > N: # 상담에 필요한 일수가 퇴사일을 넘어가면
     dp[i] = dp[i+1] # 다음날 값 그대로 가져옴
 
 else: # 
     dp[i] = max(dp[i+1], dp[t[i] + i] + p[i]) 
     # 오늘(i) 상담을 안 할 경우와 오늘 상담을 할 경우 중 max 값
     # 오늘 상담을 안하니까 그 전 단계 dp[i+1] 가져오기 
     # p[i] (그날의 상담 수익) + dp[i + t[i]] (그 이후 얻을 수 있는 최대 수익)
 print(dp)

print(dp[0])