[BOJ/백준][Silver1] 16194 : 카드 구매하기 2 (C++)

https://www.acmicpc.net/problem/16194

16194번: 카드 구매하기 2

 

 

[난이도] Silver1
[유형] DP

 

[풀이]
DP[i] : 카드 i개를 구매하기 위해 지불해야 하는 최솟값

dp[i] = min(dp[i],dp[i-j]+P[i])

 

#include <cstdio>
#include <algorithm>
using namespace std;
int N,P[1001],dp[1001];
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&P[i]);
    for(int i=1;i<=N;i++) dp[i]=1e8;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(i-j>=0) dp[i]=min(dp[i],P[j]+dp[i-j]);
        }
    }
    printf("%d",dp[N]);
} 

 

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/16194.cpp