[알고리즘] dp - 백준 25644 1904 11060 1309 15486

 

25644 최대 상승

import sys
input = sys.stdin.readline
n = int(input())

nums = list(map(int, input().split()))

ans, benefit = 0, 0

for i in range(len(nums)-1, -1, -1):
    benefit = max(benefit, nums[i])
    ans = max(ans, benefit - nums[i])

print(ans)

 

1904 01타일

n = int(input())
dp = [0 for _ in range(n+1)]
dp[0] = 1                   
dp[1] = 1             

if n > 1:
    dp[2] = 2
    for i in range(3, n+1):
        dp[i] = (dp[i-1] + dp[i-2])%15746
        
print(dp[n])

 

11060 점프 점프

import sys

input = sys.stdin.readline

n = int(input())

miro = list(map(int, input().split()))

dp = [n+1] * n

dp[0] = 0

for i in range(n):
    for j in range(1, miro[i] + 1):
        if i + j >= n:
            break
        dp[i+j] = min(dp[i+j], dp[i] + 1)

print(dp[n-1] if dp[n-1] != n+1 else -1)

 

1309 동물원

n = int(input())

dp = [0] * (n+1)

if n == 1:
    print(3)
else:
    dp[0] = 1
    dp[1] = 3
    for i in range(2, n+1):
        dp[i] = (dp[i-1]*2 + dp[i-2])%9901
    print(dp[-1]%9901)

 

15486 퇴사 2

 

import sys
input = sys.stdin.readline
n = int(input())

t, p = [], []

dp = [0 for _ in range(n+1)]

for _ in range(n):
    tt, pp = map(int, input().split())
    t.append(tt)
    p.append(pp)
    
k = 0
for i in range(n):
    k = max(k, dp[i])
    if i + t[i] > n:
        continue
    dp[i + t[i]] = max(k + p[i], dp[i + t[i]])
    
print(max(dp))