Programmers : 거스름돈

문제링크

풀이요약

DP

풀이상세

1. $n+1$ 만큼의 배열을 만들어서 $n$ 번째 인덱스까지의 모든 경우의 수를 구한다.

2. 예를 들어 [1,2,5] 를 기준으로 한다면, 1이 나오는 경우는 1개 (1), 2가 나오는 경우는 총 2개 (1,1),(2), 3이 나오는 경우는 총 2개이다. (1,1,1),(1,2)

3. 이는 $n$원에서 money[i]의 원래 경우의 수와 money[i] 만큼을 제외하고 남은 값의 경우의 수를 합한 값이 된다.

4. 경우의 수를 더할 때 모듈러 연산을 진행해야 하는 점을 잊지말자.

#include <string>
#include <vector>
using namespace std;
const int DIV = 1e9+7;
int solution(int n, vector<int> money) {
    vector<int> v(n+1,0);
    for(int i=0; i<money.size(); i++) {
        v[money[i]]++;
        for(int j=money[i]+1; j<=n; j++) {
           v[j]+=v[j-money[i]]%DIV; 
        }
    }
    return v[n] % DIV;
}