[BeakJoon 2204] 동전 2

안녕하세요. 이번 포스팅에서는 백준 2204 동전 2 문제를 풀어보도록 하겠습니다.

 

해당 문제는

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

2294번: 동전 2

 

위 링크에서 확인하실 수 있습니다.

 

 

동전의 조합을 사용하여 만들 수 있는 가치의 최솟값을 묻는 문제입니다.

 

이러한 류의 문제는 보통 Dynamic Programming으로 접근이 가능합니다.

 

2중 루프를 돌며,

 

첫 번째 루프에서는 동전의 가치를

두 번째 루프에서는 0부터 만드려는 최종적인 가치를 돌면서, 

 

현재 값이 현재 동전을 사용하여 만들 수 있는 경우라면,

현재 값에 저장되어있는 개수와 현재 동전을 사용하기 전의 가치 + 1 중 최솟값을 저장해주시면 됩니다.

 

코드를 보시면 훨씬 이해가 빠르실거라 생각합니다.

 

<소스 코드>

#include <bits/stdc++.h>
using namespace std;

int n, k, dp[100004];
vector<int> v;
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> k;
	
	for(int i = 0; i < n; i++) {
		int a; cin >> a;
		v.push_back(a);
	}
	
	fill(dp, dp+100004, 1e9);
	for(auto coin : v) dp[coin] = 1;
	for(auto coin : v) {
		for(int j = 0; j <= k; j++) {
			if(j-coin >= 0) dp[j] = min(dp[j-coin]+1, dp[j]);
		}
	}
	if(dp[k]!=1e9)cout << dp[k];
	else cout<<"-1";
	
	return 0;
}

 

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.