[알고리즘] 백준 - 퇴사2

백준 - 퇴사2

내 예전 풀이

N = int(input())
arr = []

for i in range(N):
    t, p = map(int, input().split())
    arr.append([t, p])

dp = [0] * (N+1) # dp[i] = i 일까지 일했을 때 최대 값

tmp_max = 0
for i in range(N):
    tmp_max = max(tmp_max, dp[i])

    if i + arr[i][0] > N:
        continue

    dp[i + arr[i][0]] = max(tmp_max + arr[i][1], dp[i + arr[i][0]])

print(max(dp))

예전에 풀었던 문제인데 풀지 못했다. 대신 확실하게 다시 알고 넘어가자.

앞에서부터 뒤로 채워간다. dp[i] = i일까지 일했을 때 최대 값이다. 그래서 만약 최대 일하는 날짜를 넘어가면 해당 해당 값을 채우지 않는다. i날까지 일했을 때 최대 값은 항상 i-1이하 날까지의 최대값 이상이다. 그리고 오늘 일할 수도 안할수도 있으니 그 둘중 최대값을 i일의 최대값으로 유지를 한다.