[백준] 동전1 2293번 (c++)

출처 : 2293번: 동전 1 (acmicpc.net)

2293번: 동전 1

풀이 방법

dp를 활용해서 풀이하는 문제이다.

0에서 n번째 까지 동전이 있는데 이중 for 문을 돌며 0번째 동전만 사용했을 때부터 n번째 동전까지 다 사용한 경우까지

더하면 된다.

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

}

위 코드에서 c[i]는 동전 가치를 저장한 배열이다.  

dp[j] += dp[j -c[i]]가 뜻하는 건 예를 들면 j가 5이고 c[i]가 2라면 5원을 만드는 경우중 2원짜리 동전을 포함하는 경우는

3원을 만드는 경우(2원 짜리 동전을 사용하지 않고 만든 경우)와 같다 왜냐하면 3원에다가 2원짜리 동전 하나만 추가하면 5원이 되기 때문이다. 

이런 방식으로 이중 for문을 돌며 c[i]가치 동전을 사용하여 만든 경우를 추가해 주면 된다.

#include <bits/stdc++.h>
using namespace std;

int n, k;
int c[101];
int dp[10001];
int main() {
    cin >> n >> k;
    for (int i = 1;i <= n;i++) {
        cin >> c[i];
    }
    memset(dp, 0, sizeof(dp));
    dp[0] = 1; //0원을 만드는 경우의 수는 1이라고 하자
    for (int i = 1;i <= n;i++) {
        for (int j = c[i];j <= k; j++) {
            dp[j] += dp[j - c[i]];
        }
    }
    cout << dp[k];
    return 0;
}