알고리즘 문제 풀기
<백준> 2294번 동전2
studying develop
2020. 4. 16. 17:42
//
// 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으로 했었어서 값이 계산이 제대로 안됬다. 이제 스위프트로 짜보자 ㅋㅋ