백준, BOJ, 11057번, 오르막 수 : C++ [CPP]

이 문제도

 DP다.

과연 N번째 동전은 어느 것을 가져와야할까?를 생각해보자

N-1번째 동전은 무엇을 쓰는 것이 좋을까 생각해보자

 

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

 

---

 

#맞는 풀이

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

using namespace std;

const int MAX = 10001;

int N,K;
int dp[MAX];

vector<int> vec;




int main(){
    cin >> N >> K;
    fill(dp, dp+10001, MAX);
    //우선 min에 걸리지 않게 충분히 크게 MAX로 초기화
    
    for(int i = 0; i<N; i++){
        int x;
        cin >> x;
        vec.push_back(x);
        if(x>10000)continue; //어차피 K보다 가치가 큰 동전은 쓰지 않음
        dp[x] = 1; //해당 동전은 무조건 1개로 쓸 수 있음
        
    }
    
    
    for(int i = 1; i<=K; i++){
        for(auto x : vec){
            int temp = i - x;
            if(temp <= 0)continue; // 해당 가치를 만들기 위해선 그 동전을 써서는 안됨.
            dp[i] = min(dp[i], dp[temp] + 1); //가장 작은 값을 택함.
        }
    }
    
    if(dp[K] >= MAX) cout << "-1";
    else cout << dp[K];
    
    

    
    
    return 0;
}