[BOJ] 2294 | 동전 2

문제

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

풀이

https://www.acmicpc.net/problem/2293을 풀면 사고를 확장하여 쉽게 풀 수 있다.

DP[i]를 i번 동전을 만들 수 있는 최소 횟수라고 정의하면,

DP[i] = max(DP[i], DP[ i - coin[j] ] + 1), j = 0~n-1 로 정리된다.

위 점화식을 그대로 적용하면 AC를 받게된다.

시간복잡도는 동전 1과 같은 O(NM).

소스

#include<iostream>
#include<algorithm>
#define MAX 10000001
using namespace std;

int n, k, dp[10010], coin[101];
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	for (int i = 0; i <n; i++)
		cin >> coin[i];
	for (int i = 1; i <= k; i++)
		dp[i] = MAX;
	sort(coin, coin + n);
	for (int j = 0; j < n; j++)
		for (int i = 1; i <= k; i++)
			if (i >= coin[j])
				dp[i] = min(dp[i - coin[j]]+1, dp[i]);
	if (dp[k] == MAX)
		cout << -1;
	else
		cout << dp[k];
}