[백준 14501 퇴사 문제] PYTHON

 

dp라는 리스트를 하나 만들고 해당 배열의 index들을 일로 설정해놨다.

index의 값은 T,P를 for문으로 돌며 해당 일에 벌 수 있는 최대의 수익으로 초기화하거나 더한다. 

예를 들어 위의 상담 일정표를 예로 들면

1일: [0, 0, 0, 10, 10, 10, 10, 10]   (3일 후부터 10을 벎)
2일: [0, 0, 0, 10, 10, 10, 20, 20]   (6일 후부터 20을 벎)
3일: [0, 0, 0, 10, 10, 10, 20, 20]
4일: [0, 0, 0, 10, 30, 30, 30, 30]
5일: [0, 0, 0, 10, 30, 30, 45, 45]
6일: [0, 0, 0, 10, 30, 30, 45, 45]

7일: [0, 0, 0, 10, 30, 30, 45, 45]
마무리일: [0, 0, 0, 10, 30, 30, 45, 45]

 

이런 식으로 계산을 진행한다.

그러면 마지막 index의 값이 최대 벌 수 있는 값으로 나온다.

 

N = int(input())
costs=[]
dp=[0]*(N+1)
for _ in range(N):
    costs.append(list(map(int, input().split())))
costs.append([0,0])
for i in range(N+1):
    date=costs[i][0]
    cash=costs[i][1]
    for j in range(i+date,N+1):
        if(dp[j] < cash+dp[i]):
            dp[j] = cash+dp[i]
print(dp[-1])