[백준][Python][14501][15486][DP]퇴사, 퇴사2

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

14501번: 퇴사

문제:https://www.acmicpc.net/problem/15486

15486번: 퇴사 2

DP 문제다.

둘 다 푸는 방법은 같고 개수만 15, 1500000개로 다르다. 따라서, 퇴사 1 은 O(N^2)로 풀어도 되지만 퇴사 2는 O(N)으로 풀어야 한다.

 

i 번째 날, 일을 선택했을 때는 

i 번째에 일을 선택해서 t[i]까지 한 값 = max(i번째까지 와서 벌은 돈의 최댓값 + 현재 i번째 일을 할 경우, 일을 안 하고 넘어갈 경우)

 

로 풀 수 있다.

 

import sys

n = int(input())
t,p = [],[]
dp = [0]*(n+1)

for i in range(n):
    tmp = [int(i) for i in sys.stdin.readline().split()]
    t.append(tmp[0])
    p.append(tmp[1])
cmax = 0
for i in range(n):
    cmax = max(cmax,dp[i])
    if i+t[i] > n:
        continue
    dp[i+t[i]] = max(cmax+p[i], dp[i+t[i]])

print(max(dp))