Algospot - [COINS] CoinChange

Coin Change

문제

우리 나라에는 10원, 50원, 100원, 500원의 네 가지 동전이 있다. (1원짜리와 5원짜리는 거의 안 쓰니까 없는 걸로 하지요) 이 동전들을 이용해 110원을 거슬러 주는 방법은 몇 가지나 될까? 다음의 네 가지가 있다:

• 10원 짜리 11개
• 10원짜리 6개, 50원짜리 1개
• 10원짜리 1개, 50원짜리 2개
• 10원짜리 1개, 100원짜리 1개

금액이 커지거나 동전의 종류가 많아질 수록 이 경우의 수는 많아진다. 동전의 종류와 금액이 주어질 때, 해당 동전들을 이용해 해당 금액을 환전하는 방법의 수를 구하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 수 T (1 <= T <= 100) 가 주어진다. 각 테스트 케이스의 첫 줄에는 환전할 금액 M (1 <= M <= 5000) 과 동전 종류의 개수 C (1 <= C <= 100) 가 주어진다. 그 다음 줄에, C 개의 정수로 각 동전 종류별 금액이 주어진다. 동전의 금액은 5000 이하의 자연수이다.

출력

각 테스트 케이스마다, 해당 금액을 환전할 수 있는 경우의 수를 출력한다. 경우의 수가 1000000007 보다 큰 경우, 1000000007 으로 나눈 나머지를 출력한다.

예제 입력

4
110 4
10 50 100 500
850 4
10 50 100 500
3600 5
100 300 500 900 2000
1278 8
1 2 4 8 16 32 64 128

예제 출력

4
110
130
873794561

#include <stdio.h>
int testCase, nowCase;
int money, coinCount;
long int d[5002];
int coin[1002];
long int result[102];
void problem(){
    int i=0, j=0;
    d[0]=1;
    for(i=1; i<=money; i++){
        d[i]=0;
    }
    for(i=0; i<coinCount; i++){
        for(j=coin[i]; j<=money; j++){
            d[j]+=d[j-coin[i]]%1000000007;
        }
    }
    result[testCase-nowCase-1]=d[money]%1000000007;;
}
void printResult(){
    int i=0;
    for(i=0; i<testCase; i++){
        printf("%ld\n", result[i]);
    }
}
void inputValue(){
    int i=0;
    scanf("%d %d\n", &money, &coinCount);
    for(i=0; i<coinCount; i++){
        scanf("%d", &coin[i]);
    }
    getchar();
}
int main()
{
    int i=0;
    scanf("%d\n", &testCase);
    nowCase=testCase;
    while(nowCase--){
        inputValue();
        problem();
    }
    printResult();
    return 0;
}