DP > 카드 구매하기 2 (16194번)

문제

---

풀이

아 이거 앞에거 풀고 바로 풀면 안될거같은데...

앞의 카드 구매하기 문제랑 달라진건 최소 금액이라는 거다

그래서 그냥 부등호만 바꿨다.. 최소값 구하는 로직으로..

여기서 하나 유의할 점은 냅다 그렇게만 해두면 0이 결과값이 될 수 있기 때문에

만약 배열에 저장된 값이 0이면 일단 구한 값을 저장해줘야된다!

이거때매 한번 삐끗함ㅎㅎ

 

---

코드

#include <iostream>
#include <stdio.h>
#define MAX 1001

int d[MAX];
int p[MAX];

using namespace std;

int main()
{
    ///bottom-up
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n;
    int res=0;
    cin>>n;
    
    for(int i=1;i<=n;i++)
    {
        cin>>p[i];
    }
    
    d[0]=0;
    d[1]=p[1];
    
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            res=p[j]+d[i-j];
            if(d[i]==0) d[i]=res;
            else if(res<d[i]) d[i]=res;
        }
    }
    printf("%d\n",d[n]);
    return 0;
}