[Level 3] 3. 거스름돈 경우의 수

3. 거스름돈 경우의 수

Algorithm - Level 3

- 풀이

1. 이 문제도 Dynamic Programming으로 접근가능하다.

2. n+1 크기의 배열을 선언한다.

3. 1부터 n까지 원소를 0으로 초기화한다.

-> 만약, 화폐단위 중 1이 존재하면 모든 원소를 1로 초기화한다.

5. 화폐단위와 같은 거스름돈은 (n=5, money=5) 경우의 수를 1 증가한다.

6. 그 외는 n까지의 인덱스를 차례로 접근해 작은 화폐단위를 뺀 인덱스의 원소값을 더해준다.

-> ex) money=2, index=5일 경우, 5-2=3 index에 위치한 원소값을 더해준다.

이는 그 전에 계산한 경우의 수를 더해주는 것으로 거스름돈이 5인 경우의 수는 money=2를 하나 선택하고 남은 돈 3의 경우의 수와 같다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int solution(int n, vector<int> money) {
    int answer = 0;
    vector<int> dp(n+1, 0);
    
    sort(money.begin(), money.end());
    
    for(int i=0; i<money.size(); ++i){
        for(int j=1; j<dp.size(); ++j){
            if(money[i]==j || money[i]==1)
                dp[j] += 1;
            else if(j >= money[i])
                dp[j] = (dp[j] + dp[j-money[i]]) % 1000000007;
        }
    }
    
    answer = dp[n];
    return answer;
}