[C++] BOJ / 2293번 / 동전 1

2293번: 동전 1

 

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

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

입력

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

3 10
1
2
5

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

10

풀이

다이나믹 프로그래밍 알고리즘을 사용하여 풀이하였습니다.

 

배열에 저장된 모든 동전에 대한 반복문을 수행하며, 첫 번째 동전을 사용하여 k원을 만드는 경우의 수 -> 두 번째 동전을 사용하여 k원을 만드는 경우의 수 -> 세 번째 동전을 사용하여 k원을 만드는 경우의 수를 각각 구해가며 기존 dp 배열을 갱신해주었습니다.

 

또한 위의 작업을 수행하기 전 dp[0]의 값을 1로 초기화해줌으로써 'dp[1] = dp[1] + dp[0] = 0' 과 같은 예외가 발생하지 않도록 해주었습니다.

 

최종 출력 값은 dp[k]이며 이는 k원을 만드는 모든 경우의 수의 합을 의미합니다.

---

#include<iostream>

using namespace std;

int n, k;
int coin[101];
int dp[10001];

void input()
{
	cin >> n >> k;
	for (int i = 1; i <= n; ++i)
		cin >> coin[i];
}

void solve()
{
	dp[0] = 1;

	for (int i = 1; i <= n; ++i)
		for (int j = coin[i]; j <= k; ++j)
			dp[j] += dp[j - coin[i]];

	cout << dp[k];
}

void init()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

int main()
{
	init();
	input();
	solve();

	return 0;
}