[백준/14501/파이썬] 퇴사

---

소스코드

N = int(input())

work = []

for i in range (N):

  work.append(list(map(int, input().split())))

dp = [0] * (N+1)

for i in range(N):

  for j in range(i+work[i][0],N+1):

    if dp[j] < dp[i] + work[i][1]:

      dp[j] = dp[i] + work[i][1]

print(dp[-1])

---

알고리즘

work = [[3, 10], [5, 20], [1, 10], [1, 20], [2, 15], [4, 40], [2, 200]]

i = 0 일때

j = 3~ N+1 까지  => 1일차에 3일을 일할 수 있으면 4일부터 일을 하는 것

    if dp[j] < dp[i] + work[i][1]:

      dp[j] = dp[i] + work[i][1]

• dp[3] 이 dp[0] + work[0][1] 보다 작으면 갱신

=> 그 날까지 얻었던 최대 이익 + 일한 이익을 갱신해 나가는 것

dp 값

[0, 0, 0, 10, 30, 30, 45, 45]