백준 2294 동전 - C++

 

동전이 최소가 되도록 n 가지 동전을 이용해 k 원을 만든다.

n이 100가지이고 10만 보다 작거나 같은 가치이며,

k는 1만 원 이하이다.

 

사용한 동전의 구성이 같은데 순서가 다르면 같은 경우이다.

-> 순열이 아닌 조합으로 풀 수 있다.

 

가치가 같은 동전이 여러 개 있을 수 있으므로

중복된 검색은 피할 수 있다.

 

k원을 만들었을 때 동전의 최소 개수만 알면 되므로

Dynamic Programming 을 이용한다.

 

1. dp 배열 정의) dp[k] = k 원 일때 사용한 최소 동전의 개수로 정의한다.

2. 기저사례) dp[0] = 0, dp[동전 1개 가치] = 1 이 기저 사례이다.

3. 점화식) dp[i] = max(dp[i], dp[i - 동전 1개 가치] + 1) 개이다.

#include <cstdio>
#include <algorithm>

using namespace std;

int N, K;
int value[101];
int dp[100001];

int main() {
	scanf("%d %d", &N, &K);
	for (int i = 1; i <= K; ++i) dp[i] = 987654321;
	for (int i = 0; i < N; ++i) {
		scanf("%d", &value[i]);
	}

	for (int i = 0; i < N; ++i) {
		int curValue = value[i];
		for (int j = curValue; j <= K; ++j) {
			dp[j] = min(dp[j], dp[j - curValue] + 1);
		}
	}

	printf("%d\n", dp[K] == 987654321 ? -1 : dp[K]);
	return 0;
}