<백준> 2294번 동전2

//
//  main.cpp
//  algorithm_practice
//
//  Created by 김동환 on 2020/04/12.
//  Copyright © 2020 김동환. All rights reserved.
//

#include <iostream>
#include <vector>

using namespace std;
int n,k;
int dp[100001] = {0};
vector<int> vec;

int main(){
    //freopen("input.txt","r", stdin);
    
    cin >> n >> k;
    //cout << n << " "<< k << "\n";
    for(int i=0;i<n;i++){
        int tmp;
        cin >> tmp;
        vec.push_back(tmp);
    }
    
    dp[0] = 1;
    
    for(int j=0;j<vec.size();j++){
        for(int i=0;i<=k;i++){
            int w = i - vec[j];
            if(w > 0){
                dp[i] = min(dp[w]+1,dp[i]);
            }
        }
    }
    

    //cout << dfs(10,0) <<"\n";
    if (dp[k] != 0)
        cout << dp[k]  <<"\n";
    else{
        cout << -1 << "\n";
    }
    
    return 0;
}

 

 

 

이렇게 하면 될거같았는데, 안되네;

 

//
//  main.cpp
//  algorithm_practice
//
//  Created by 김동환 on 2020/04/12.
//  Copyright © 2020 김동환. All rights reserved.
//

#include <iostream>
#include <vector>

#define NUM 100001

using namespace std;
int n,k;
int dp[100001] = {0};
vector<int> vec;

int main(){
    //freopen("input.txt","r", stdin);
    
    for(int i=0;i<NUM;i++){
        dp[i] = 987654321;
    }
    
    cin >> n >> k;
    //cout << n << " "<< k << "\n";
    for(int i=0;i<n;i++){
        int tmp;
        cin >> tmp;
        vec.push_back(tmp);
    }
    
    dp[0] = 0;
    
    for(int j=0;j<vec.size();j++){
        for(int i=0;i<=k;i++){
            int w = i - vec[j];
            if(w >= 0){
                dp[i] = min(dp[w]+1,dp[i]);
            }
        }
    }
    //cout << dp[15] << "\n";

    //cout << dfs(10,0) <<"\n";
    if (dp[k] != 987654321)
        cout << dp[k]  <<"\n";
    else{
        cout << -1 << "\n";
    }
    
    return 0;
}

 

아 이거다 k>0으로 했었어서 값이 계산이 제대로 안됬다. 이제 스위프트로 짜보자 ㅋㅋ