풀이 방법
- 첫 번째 동전만 사용하여 k가 되도록 하는 경우의 수를 구한다.
- 첫 번째 동전부터 두 번째 동전까지 사용하여 k가 되도록 하는 경우의 수를 구한다.
- n번째 동전까지 이를 반복한다.
이와 같은 과정으로 표를 만들어본다면 다음과 같다.
여기서 행은 동전의 가치이고, 열은 k이다.
첫 번째 동전만 사용한 경우
0 1 2 3 4 5 6 7 8 9 10
0 1 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1두 번째 동전까지 사용하는 경우
0 1 2 3 4 5 6 7 8 9 10
0 1 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 2 2 3 3 4 4 5 5 6세 번째 동전까지 사용하는 경우
0 1 2 3 4 5 6 7 8 9 10
0 1 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 2 2 3 3 4 4 5 5 6
5 1 1 2 2 3 4 5 6 7 8 10이렇게 도표를 통해 1원, 2원, 5원 동전을 사용하여 10원을 만드는 경우의 수를 구할 수 있다.
그럼 이제 규칙을 찾아 코드로 구현하면 된다.
만약 현재 사용 중인 동전의 가치가 k보다 낮은 경우에는 해당 동전을 통해 만들 수 있는 경우가 존재하지 않기 때문에 이전에 사용했던 동전의 경우의 수를 그대로 사용하면 된다.
그럼 같거나 높은 경우에는 어떻게 해야 할까?
그 경우에는 해당 동전을 사용하지 않은 상태에서의 경우의 수와 해당 동전을 사용한 상태에서의 경우의 수를 더하면 된다.
전자의 경우에는 이전에 사용했던 동전으로 k값을 만드는 경우의 수를 그대로 사용하면 되고, 후자의 경우에는 해당 동전으로 k - 현재 동전 가치 값을 만드는 경우의 수를 사용하면 된다.
즉, 다음과 같은 점화식이 만들어진다.
P[i] : i번째 동전의 가치, DP(i, k) : i번째 코인을 사용하여 k값을 만드는 경우의 수
DP(i, k) = DP(i - 1, k) (P[i] < k)
DP(i, k) = DP(i - 1, k) + DP(i, k - P[i]) (P[i] >= k)이 점화식을 사용하여 코드를 구현할 수 있겠지만, 이 문제에서 사용 가능한 메모리의 양은 4MB밖에 되지 않기 때문에 이 부분도 고려를 해야한다.
위와 같은 도표의 데이터를 모두 저장하기 위해 dp[100][10001]와 같은 배열을 선언하게 되면 사용 가능한 메모리 양을 초과하게 된다.
그런데, 도표를 확인해보면 저 방식의 배열을 사용하지 않아도 충분히 값을 구할 수 있다.
dp[10001] 과 같은 배열을 선언한 후, 현재 사용 중인 코인의 가치보다 k가 작은 경우에만 현재 값에 dp[k - P[i]] 값을 더해주면 된다.
그럼 다음과 같은 코드를 작성할 수 있다.
해당 방법으로 작성한 소스 코드
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n, k, dp[10001] = { 0 }, val[101];
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%d", &val[i]);
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
if (val[i] <= j) dp[j] += dp[j - val[i]];
}
}
printf("%d \n", dp[k]);
return 0;
}