[백준] [DP] 11052. 카드 구매하기

11052. 카드 구매하기

11052번: 카드 구매하기첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

 

• 풀이
  • 돈을 최대한 많이 지불해서 카드 N개 구매
  • Pn= n개 카드 한번에 구매하는데 드는 비용
    • n의 약수인 i : Pi 을 n//i번 하는거랑 Pn을 한번 하는것중에 뭐가 더 비싼가?
    • Pi 랑 P(n-i)를 더한 값이랑 Pn 중 뭐가 더 비싼가?
  • n보다 앞의 값들이 다 존재해야함
    • 다음 수를 만들 수 있는 모든 경우를 가장 비싼값으로 업데이트 해가면서 n까지 와야함

# 돈을 최대한 많이 지불해서 카드 N개 구매
n = int(input())
card = [0]+list(map(int, input().split()))
dp = [0]*(n+1)

for i in range(1, n+1):
    dp[i] = max(dp[i], card[i])
    for j in range(1, i):
        if i % j == 0:
            dp[i] = max(dp[i], dp[j]*(i//j))
        dp[i] = max(dp[i], dp[j]+dp[i-j])

print(dp[n])