[백준 2294] 동전 2

요구사항

주어진 동전을 최소로 이용하여 금액 맞추기

 

풀이

처음 접한 유형의 문제라서 어려웠다

일단 O(2^n)으로 풀면 시간 초과이다

 

dp를 이용한다

1~max 금액까지 탐색한다

현재 금액만 사용했을때 최소 몇개로 금액을 달성 할 수 있는가 본다

문제 예시

1원 사용할때는

1~15원까지 각 개수 만큼 사용 1, 2, 3, 4 - 15까지

5월 사용할때는

5원은 1개

6원 1원 + 5원

7원 2원 + 5원 식으로 증가

 

점화식은 d[i] =min(d[i], d[i - coin[now] +1)로 세울 수 있다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int dp[10001] = { 0, };
int n, k, coin[101];
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= k; i++) dp[i] = 10001;

	for (int i = 1; i <= n; i++) scanf("%d", &coin[i]);
	
	for (int i = 1; i <= n; i++) 
		for (int j = coin[i]; j <= k; j++) 
			dp[j] = min(dp[j], dp[j - coin[i]] + 1);
			
	if (dp[k] == 10001) cout << "-1" << endl;
	else cout << dp[k] << endl;
}