반응형
728x170
이 문제도
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;
}
728x90
반응형
그리드형
'문제풀이(Problem Solving)' 카테고리의 다른 글
백준, BOJ, 11048번, 이동하기 : C++ [CPP] (0) | 2021.12.29 |
---|---|
백준, BOJ, 11053번, 가장 긴 증가하는 부분 수열 : C++ [CPP] (0) | 2021.12.29 |
백준, BOJ, 11057번, 오르막 수 : C++ [CPP] (0) | 2021.12.28 |
백준, BOJ, 1915번, 가장 큰 정사각형 : C++ [CPP] (0) | 2021.12.27 |
백준, BOJ, 1389번, 케빈 베이컨의 6단계 법칙 : C++ [CPP] (0) | 2021.12.27 |