카드 구매하기 2

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

16194번: 카드 구매하기 2

최솟값 구하기

d[n] = min(d[i], d[i - j] + p[j])    1<=j<=i

 

방법 1

d를 1000 * 10000(최댓값)으로 초기화

 

방법 2

d를 -1로 초기화 -> d가 -1이면 아직 계산을 안한것

비교를 하려면 일단 들어는 가야하니까!!

vector<int> d(n+1, -1) --> -1로 초기화

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    vector<int> p(n + 1);
 
    for (int i = 1; i <= n; i++)
        cin >> p[i];
 
    vector<int> d(n + 1, -1);
 
    d[0] = 0;
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            if(d[i] == -1 || d[i] > d[i-j] + p[j])
                d[i] = d[i - j] + p[j];
        }
    }
 
    cout << d[n];
 
}