백준 9084번 동전

문제 링크입니다: https://www.acmicpc.net/problem/9084

http://jaimemin.tistory.com/362과 동일한 문제였습니다.

/*

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다.

이 동전들로는 모두 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다.

예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.

동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.

*/

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 20;

const int MONEY = 10000;

 

int N, M;

int coinValue[MAX];

int cache[MONEY + 1];

 

int numOfWays(void)

{

        memset(cache, 0, sizeof(cache));

        cache[0] = 1; //0원

        //M 이하 합에 대해 경우의 수를 모두 구한 뒤 차례차례 더한다

        for (int i = 0; i < N; i++)

               for (int j = coinValue[i]; j <= M; j++)

                       cache[j] += cache[j - coinValue[i]];

        return cache[M];

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 1 || test_case>10)

               exit(-1);

 

        for (int i = 0; i < test_case; i++)

        {

               cin >> N;

               if (N<1 || N>MAX)

                       exit(-1);

               for (int i = 0; i < N; i++)

                       cin >> coinValue[i];

               cin >> M;

               if (M<1 || M>MONEY)

                       exit(-1);

               cout << numOfWays() << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~