[C++] 백준 2293 동전 1 DP

풀이

예시: 1,2,5를 사용해 10 만들기, 단 중복집합x

1. 먼저, 1을 사용해 x원을 만들 때 가능한 경우는 모두 1가지 뿐이다. DP표에 각 수를 만들 수 있는 경우의 수를 저장한다.

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

2. 2를 사용하는 경우를 따져보자. x원을 만든다고 했을 때, 2를 사용해 x를 만드려면 이전 값은 x-2 이어야 한다.

단순히 x-2에 2를 추가해주면 x가 만들어진다. 

2를 사용해 2을 만드는 방법은 한 가지.

그럼 2를 사용해 3을 만드는 경우는?

1원을 만드는 모든 경우의 수에서 2원을 추가해주면 된다. 따라서 1원을 만드는 모든 경우의 수인 1가지이다. (1 + 2 = 3)

그렇다면 이때, 1원과 2원을 사용해서 3을 만드는 모든 경우의 수는?

1을 사용해 3을 만드는 경우 1가지 + 2를 사용해 3을 만드는 경우 1가지 = 2가지 (1,1,1 / 1, 2) 이다.

추가로 4를 만들어보자.

2를 사용해 4를 만드려면 2를 만드는 경우의 수에 2만 추가하면 된다. (1,1 / 2) + 2 => 2가지

그리고 1을 사용해 4를 만드는 경우를 더해주면 된다.  (1, 1, 1, 1) = 1가지

총 3가지 경우다. DP표를 업데이트 하면 다음과 같다.

1	2	3	4	5	6	7	8	9	10
1	(1+1)=2	(1+1)=2	(1+2)=3	(1+2)=3	(1+3)=4	(1+3)=4	(1+4)=5	(1+4)=5	(1+5)=6

이제 5를 사용하는 경우에 대해 표를 업데이트 하자.

이때 5를 사용해 4까지는 만들 수 없으므로 위의 경우의 수를 그대로 가져온다. 

5를 만드는 모든 경우는 5를 하나 사용하는 경우와 1, 2를 사용해 5를 만드는 경우의 수를 더하는 것이다.

나머지는 앞과 동일하다.

5를 사용해 6을 만들기 위해서는 1을 만들 수 있는 모든 경우의 수가 필요하다.

따라서 DP[x-5]의 경우의 수를 DP[X]와 더하면 된다. 

따라서, 다음과 같은 점화식이 성립한다.

DP[x] = DP[x] + DP[x - coin]

1	2	3	4	5	6	7	8	9	10
1	2	2	3	(3+1)=4	(4+1)=5	(4+2)=6	(5+2)=7	(5+3)=8	(6+4)=10

모든 동전에 대해 한번씩 업데이트 하면 문제가 해결된다. 

 

리뷰

중복집합이 없어야 한다는 조건 때문에 난해한 문제였다. 하지만 이는 각 동전을 한번씩 사용하는 for loop를 차례대로 돌기 때문에 1을 사용하고 2를 사용하는 경우만 존재할 뿐, 2를 먼저 사용하고 1을 사용하는 경우는 존재하지 않게 되었다. 그리고 나머지 과정은 2xn 타일링 문제와 비슷한 아이디어였다.

#include <iostream>
#include <cstring>

using namespace std;

int n, m;
int arr[101];
int dp[10001];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);
    // freopen("2293.txt", "r", stdin);
	memset(dp, 0, sizeof(dp));
	memset(arr, 0, sizeof(arr));
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = arr[i]; j <= m; j++) {
			if (dp[j - arr[i]]) {
				dp[j] += dp[j-arr[i]];
			}
		}
	}

    // for (auto i : dp) {
    //     cout << i << " ";
    // }
    // cout << endl; 
	cout << dp[m];
}