[acmicpc.net] 2293 동전 1

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

문제 내용

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

소스코드

#include <iostream>
using namespace std;
 
int main() {
    int n, k;
    int *value;
    int **result;
    cin >> n >> k;
    value = new int[n];
    result = new int*[2];
    for(int i=0; i<n; i++){
        cin >> value[i];
    }
    for(int i=0; i<2; i++){
        result[i] = new int[k+1];
    }
    result[0][0] = 1;
    for(int i=1; i<=n; i++){
        for(int j=0; j<=k; j++){
            result[i&1][j] = result[(i+1)&1][j] + (j>=value[i-1] ? result[i&1][j-value[i-1]] : 0);
        }
    }
    cout << result[n&1][k];
    return 0;
}