https://www.acmicpc.net/problem/11052
시간 1초, 메모리 256MB
input :
- N (1 ≤ N ≤ 1,000)
- Pi (1 ≤ Pi ≤ 10,000)
output :
- N개를 갖기 위해 지불해야 하는 금액의 최댓값
조건 :
- 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7
- 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.
- P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우 카드가 1개 들어있는 카드팩을 4번 사면 20원
- P1 = 3, P2 = 5, P3 = 15, P4 = 16인 경우 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값
DP를 채우기 위해 현재 계산하는 것이 4라면.
4가 될수 있는 경우.
P[4]
DP[1] + DP[3]
DP[2] + DP[2]
이 세 가지중 최댓값을 넣어주는 것.
다른 경우는 없나요?
DP에 들어 갔다는 것 자체가 각 N개를 살 때의 최댓값을 넣어놓은 것이기 때문에 신경 쓸 필요가 없다.
import sys
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
dp = [0]
for item in data:
dp.append(item)
for i in range(2, n + 1):
for j in range(1, (i // 2) + 1):
dp[i] = max(dp[i], dp[j] + dp[i - j])
print(dp[n])
