[BOJ] 백준 1535 안녕 / 동적 계획법(Dynamic-Programming)

이미지를 클릭하면 문제 사이트로 이동합니다.

 

 

💭 문제 이해

 

세준이 체력이 최대 100이므로 숫자를 증가시키면서 해당 체력내에 얻을 수 있는 최대 기쁨을 갱신한다.

 

 

 

 

구현 언어: Python

 

import sys

r = sys.stdin.readline

n = int(r())
hp_loss = list(map(int, r().split()))
pleasure = list(map(int, r().split()))
dp = [[0]*101 for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(100):
        if j < hp_loss[i-1]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-hp_loss[i-1]] + pleasure[i-1])

print(dp[n][99])