백준 알고리즘 14501번 퇴사(python)

처음에는 아래와 같이 첫날부터 확인하는 방식으로 풀었다. 

N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]
dp = [0 for _ in range(N+1)]

for i in range(N):
    for j in range(i + li[i][0], N+1):
        if dp[j] < dp[i] + li[i][1]:
            dp[j] = dp[i] + li[i][1]

print(dp[-1])

통과되긴 해도 일단 반복문이 2개라 아래 사진과 같이 무의미한 동작이 상당히 많다.

반복문 하나로 끝낼 방법이 없을까 하다가 그냥 마지막 날부터 확인하면 되겠다는 생각이 들어 아래와 같이 수정했다.

N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]
dp = [0 for _ in range(N+1)]

for i in range(N-1, -1, -1):
    if i + li[i][0] > N:
        dp[i] = dp[i+1]
    else:
        dp[i] = max(dp[i+1], li[i][1] + dp[i + li[i][0]])
    
print(dp[0])