[BOJ] 백준 2294번: 동전 2

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

2294번: 동전 2

 

기본적인 DP 문제입니다.

 

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

const int INF = 0x3f3f3f3f;
int n, k, coin, dp[10001];
set<int> coins;

void solve(){
	memset(dp, 0x3f, sizeof(dp));
	dp[0] = 0;
	for(int i = 1; i <= k; ++i){
		for(int c : coins){
			if(i-c < 0) continue;
			if(dp[i] > dp[i-c]+1) dp[i] = dp[i-c]+1;
		}
	}
	if(dp[k] == INF) cout << -1;
	else cout << dp[k];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;
	while(n--){
		cin >> coin;
		coins.insert(coin);	
	}
	
	solve();
}

 

이전 포스트들의 dp 풀이와 마찬가지로 1) table 정의 2) 점화식 찾기 3) 초기값 설정의 3단계로 일관성있게 풀이했습니다.

 

1) table 정의

dp[i] : i원을 만드는데 필요한 동전의 최소 개수

 

2, 3) 점화식 찾기 및 초기값 설정 

dp 배열 INF로 초기화 (이 때 동전의 가치가 최소 1원이고, k가 최대 10,000이므로 INF의 값으로는 10,001 이상의 수로 설정하면 됩니다. 저는 integer overflow가 나지 않으면서 memset으로 간편하게 초기화할 수 있는 0x3f3f3f3f를 사용했습니다.)
dp[0] = 0 (0원을 만드는데 사용할 동전의 개수는 0입니다.)

for(int i = 1; i <= k; ++i){
	for(int c : coins){
		if(i-c < 0) continue;
		if(dp[i] > dp[i-c]+1) dp[i] = dp[i-c]+1;
	}
}

 

유의할 점은 입력으로 가치가 같은 동전이 여러 번 주어질 수 있으므로 중복을 허용하지 않는 set 자료구조를 이용했다는 것입니다.

 

시간복잡도는 반복문에서 드러나듯이 O(kn)입니다.