백준 2624번 동전 바꿔주기

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

거스름돈을 바꿔줄 때 해당 동전을 사용하지 않는 경우도 고려해야합니다.

따라서 (0 ~ 해당 동전의 갯수)까지 모두 고려해야 맞출 수 있는 문제였습니다.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAXCURRENCY = 10000 + 1; //0 < T <= 10000

const int MAX = 100;

 

int T, k;

pair<int, int> p[MAX]; //지폐의 금액과 개수

int cache[MAXCURRENCY][MAX];

 

int numOfWays(int cash, int idx) //idx는 p의 idx

{

        //기저 사례

        if (cash == 0)

                 return 1;

        if (idx >= k)

                 return 0;

 

        int &result = cache[cash][idx];

        if (result != -1)

                 return result;

       

        result = 0;

        //해당 동전을 사용하지 않는 경우 + i개 사용하는 경우

        for (int i = 0; i <= p[idx].second; i++)

                 //cash는 음수일 수 없다

                 if (cash - (p[idx].first * i) >= 0)

                         result += numOfWays(cash - (p[idx].first * i), idx + 1);

 

        return result;

}

 

int main(void)

{

        cin >> T >> k;

 

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

                 cin >> p[i].first >> p[i].second;

 

        memset(cache, -1, sizeof(cache));

 

        cout << numOfWays(T, 0) << endl;

        return 0;

}

개발환경:Visual Studio 2017

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