문제 풀이/백준
BOJ 2294번: 동전 2
danbibibi
2022. 12. 9. 15:13
문제
문제 바로가기> BOJ 2294번: 동전 2
2294번: 동전 2
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주
www.acmicpc.net
풀이
dp[j] : 가치의 합 j를 만드는 데 사용한 동전의 최소 개수
1. j == coin[i] 인 경우,
동전 하나만으로 j를 만들 수 있으므로, dp[j] = 1
2. j > coin[i] 인 경우,
해당 동전을 사용해서 더 적은 동전으로 j를 만들 수 있는지, dp[j] = min(dp[j], dp[j-coin[i]]+1)
#include<iostream>
#define INF 987654321
using namespace std;
int n, k;
int coin[101], dp[10001];
void input(){
cin >> n >> k;
for(int i=1; i<=n; i++) cin >> coin[i];
for(int i=1; i<=k; i++) dp[i] = INF;
}
void solution(){
for(int i=1; i<=n; i++){
for(int j=1; j<=k; j++){
if(j == coin[i]) dp[j] = 1;
if(j > coin[i]) dp[j] = min(dp[j], dp[j-coin[i]]+1);
}
}
if(dp[k] == INF) cout << -1;
else cout << dp[k]; // 사용한 동전의 최소 개수
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
input();
solution();
}