[BOJ] 2293번: 동전 1

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/2293

2293번: 동전 1

 

아주 아주 유명한 dp 문제다.

 

dp[$k_j$] = 가치의 합이 $k_j$원이 되게 하는 경우의 수

즉, dp[5]의 경우 5원을 만들 수 있는 경우의 수를 저장한다.

 

이 문제를 풀기 위한 점화식은

dp[$k_j$] = dp[$k_j$] + dp[$k_j$ - coin[i]]

 

이때 주의할 점은 초기값 dp[0]을 설정해줘야 함이다.

그 값을 뭘로 설정해줘야 할지는 조금만 생각해보면 알 수 있다.

 

문제의 예제를 통해 알아보자.

1원, 2원, 5원의 3가지 동전이 있고, 이 동전들을 이용해서 10원을 만들 수 있는 경우의 수를 묻고 있다.

 

먼저 1원을 사용해서 1원부터 10원까지를 만들 수 있는 경우의 수를 찾아보자.

 

1원으로 합이 1원이 되도록 하는 경우의 수는 1원 한 개를 사용하는 방법 즉, 1이다.

점화식에 적용해보면, dp[1] = dp[1] + dp[1 - 1]

                                    = dp[1] + dp[0]

임을 알 수 있다.

현재 dp[1]은 0으로 초기화되어 있고, dp[0]은 특정한 값으로 초기화되어 사용되어야 한다.

그 값은 어렵지 않게 1임을 알 수 있다.

dp[0] = 1로 초기화되어야 $k_j$원의 동전을 사용해서 $k_j$원을 만드는 경우의 수(= 1)을 계산할 수 있다.

 

그럼 2원을 통해 2원을 만들 수 있는 경우의 수를 계산해보자.

점화식에 의해 dp[2] = dp[2] + dp[2 - 2]임을 알 수 있다.

여기서 우변의 dp[2]는 앞서 1원을 통해 2원을 만든 경우의 수를 누적하기 위함이다.

따라서 dp[2] = 1 + 1 = 2로 계산할 수 있다.

 

이제 아래 표를 모두 채워보자.

 

	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	X	2	2	3	3	4	4	5	5	6
5	X	X	X	X	4	5	6	7	8	10

 

 

/*
20200515
baekjoon 2293번 - 동전 1
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, k; int coin[101]; int dp[10001];
int main() {
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	int ans = 0, sum = 0;
	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		cin >> coin[i];
	}

	dp[0] = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = coin[i]; j <= k; ++j) {
			dp[j] = dp[j] + dp[j - coin[i]];
			//cout << dp[j] << " ";
		}
		//cout << "\n";
	}

	cout << dp[k];
}