[백준] 2294번 - 동전 2 (C++)

2294번: 동전 2

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

 

 

 

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

 

 

 

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

 

풀이과정

문제에서 요구하는 사항은 k라는 값을 만들기위해서 필요한 동전에 최소개수를 구하라 라는 문제였었다.

문제의 유형자체가 전에 풀었던 동전 1에 비해서는 나름 친숙했던 문제였어서 쉽게 접근할 수 있었던 거 같다.

 

문제에서 요구하는 k를 만들기 위한 동전의 최소개수를 구하는 방법은 

dp[k] = (dp[k - (동전의 종류)] + 1) 중 최소 값이었다. 

dp[k - (동전의 종류)]라는 값은 k보다 작은 값들을 구하는 동전에 최소개수를 구해온 과정이고,

dp[k - (동전의 종류)]는 다양한 동전의 종류 중에서도 그 중에 가장 작은 값이 있을 것이기때문에 비교를 해가면서 가장 작은 dp[k]라는 값을 구하는 방식으로 코드풀이를 진행하였다.

code

#include <iostream>

int		coin[101];
int		dp[10001];

int		main(void)
{
	int n, k, temp;

	std::cin >> n >> k;
	for (int i = 0; i < n; i++) {
		std::cin >> coin[i];
	}
	for (int i = 1; i <= k; i++) {
		dp[i] = 10001;
		for (int j = 0; j < n; j++) {
			if (i == coin[j])
				dp[i] = 1;
			else if (0 < i - coin[j] && dp[i - coin[j]] + 1 < dp[i]) {
				dp[i] = dp[i - coin[j]] + 1;
			}
		}
	}
	if (dp[k] == 10001) std::cout << "-1";
	else std::cout << dp[k];

	return (0);
}

 

후기

친숙했던 유형이었어서 점화식접근에 크게 오래걸리지는 않았던 거 같다.