백준 16194 - 카드 구매하기 2

문제 설명

 

 

 

 

=> 카드 구매하기 1번 문제를 참조하여 풀 수 있다. 

 

https://codingham.tistory.com/124

백준 11052 - 카드 구매하기

 

 

=> 위와 다른 것은 최솟값을 구하는 것이다. 

 

 

***주의점 

=> 카드를 구매하는 비용은 0보다 크다

=> 배열의 초기값 설정을 잘해주어야 한다.

=> D에 들어갈 수 있는 값의 최댓값은 1000 * 10000이다. ( 카드의 개수 * 카드팩의 가격 )

 

 

 for(int i=1; i<=N; i++ )
    {
        for( int j=1; j <= i; j++)
        {
            D[i] =  min(D[i], D[i - j] + P[j]);
        }

 

 

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>


using namespace std;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int N;
    cin >> N;
    
    vector<int> P(N+1);
    vector<int> D(N+1);
    
    for(int i=1; i<=N; i++)
    {
        D[i]=1000*10000;
    }
    D[0]=0;
    int tmp;
    for(int i=1; i<= N; i++)
    {
        cin >> tmp;
        P[i] = tmp;
    }
    
    
    for(int i=1; i<=N; i++ )
    {
        for( int j=1; j <= i; j++)
        {
            D[i] =  min(D[i], D[i - j] + P[j]);
        }
    }
    
    cout <<D[N] <<'\n';
    
    
}

 

 

 

 

 

실행 화면 1

 

 

실행 화면 2