BOJ 11052 카드 구매하기

LONGNEW·2021년 1월 15일
0

BOJ

목록 보기
51/333

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])

0개의 댓글