[백준] 카드 구매하기

출처::  www.acmicpc.net/problem/11052

분류:: dp

 

1. 문제 이해 및 해결과정

- dp: 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값 - dp[i] = max(  dp[i] , dp[i-j] + p[j] ) 1<=j<=i - dp[4] = max(dp[i], 3개를 가지기 위해 지불해야 하는 최대 값 + 1개 카드팩의 가격, 2개를 가지기 위해 지불해야하는 최대값 + 2개 카드팩 가격, 1개를 가지기 위해 지불해야하는 최대값 + 3개 카드팩의 가격)    => dp[4]= max( dp[i] , dp[3] + p[1] , dp[2] + p[2] , dp[1] + p[3] )

 

2. 풀이방법

  1. dp

#카드 구매하기
#https://www.acmicpc.net/problem/11052
import sys
sys.stdin = open("input.txt","r")
n=int(input())
p=[0]+list(map(int,input().split())) #카드팩 n개를 가질때 비용
dp=[0]*(n+1) #카드 n개를 가지기 위해 지불해야하는 최대금액
dp[0]=0
dp[1]=p[1]
for i in range(2,n+1):
    for j in range(1,i+1): #1~i
        dp[i]=max(dp[i],dp[i-j]+p[j])
print(dp[n])

 

3. 오답원인

 

4. 알게된 점