[Python] 백준 - 퇴사

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

 

나의 답... (틀림)

N = int(input())

ti = []
pi = []
for i in range (N):
    t = list(map(int,input().split()))
    ti.append(t[0])
    pi.append(t[1])

result = []
MAX = 0

for i in range (N):   
    for j in range(i,N,1):
        a = []
        while (j<N and j+ti[j] < N):
            a.append(pi[j])
            j += ti[j]

        print(a)

        MAX = max(MAX, sum(a))

print(MAX)

모든 경우의수를 넣어보려고 했는데, 안되네... 

내가 못찾은 경우가 있나보다. 

테스트 케이스에서는 마지막 테케가 원하는 값대로 안나왔다.

 

 

다른 사람 답

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)


for i in range(N-1, -1, -1): # 뒤에서부터 거꾸로
    if t[i] + i > N: # 상담에 필요한 일수가 퇴사일을 넘어가면
        dp[i] = dp[i+1] # 다음날 값 그대로 가져옴
    
    else:
        dp[i] = max(dp[i+1], dp[t[i] + i] + p[i]) # 오늘 상담을 안 할 경우와 상담을 할 경우 중 max 값

print(dp[0])