[2293] 동전1

이문제는 처음에 이상한 점화식 세우다가 안돼서 다시푼 문제다.

#include <cstdio>
using namespace std;
​
int main(){
    int N[2];
    int val[101];
    int d[10001] ={};
​
    scanf("%d %d",&N[0],&N[1]);
​
    for(int i = 0;i<N[0];i++){
        scanf("%d",&val[i]);
    }
    d[0] = 1;
    for(int i = 0;i<N[0];i++){
        for(int j = 0;j<=N[1];j++){
            if(j>=val[i])
                d[j] += d[j-val[i]];
        }
    }
​
    printf("%d\n",d[N[1]]);
}

우선 코인 수만큼 반복문을 돌고 그 안에서 그 코인의 값으로 만들 수 있는 숫자를 1부터 N[1]까지 d[j]에 저장한다.
이때 d[j]는 j에서 코인값을 뺀 d[j-val[i]]의 값을 더해야한다. d[j-val[i]]에 저장된 경우의 수에 현재 코인을 추가하기만 하면
숫자j를 만들 수 있기때문이다.

대신 j가 코인값보다 커야하는데 그 이유는 가령 5원짜리 동전으로 숫자 4(j==4)를 만들 수 없기 떄문이다.