[프로그래머스 lv3] 거스름돈 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

dp[K]를 주어진 동전을 사용해 K를 만드는 모든 경우의 수 라고 정의하자.

예를 들어, K = 5 이고 주어진 동전 money = [1, 2, 5] 라면, 가능한 경우는 dp{K] = 4이다.

 

1+1+1+1+1

1+1+1+2 

1+2+2

5

 

주의할 점은 1+1+1+2와 1+2+1+1, 1+1+2+1 등은 모두 같은 것이므로 중복해서 세면 안된다는 것이다.

따라서, dp[K]를 구할 때 중복이 발생하지 않도록 사용할 수 있는 동전과 금액을 차차 늘려가야 한다.

 

우선, 0을 만드는 방법은 아무것도 사용하지 않는 방법 1가지 이므로 dp[0] = 1로 설정한다.

이후, 각 동전을 끝에 추가하여 만들 수 있는 수를 확인하자.

 

money[i]를 끝에 추가할 때 만들 수 있는 수 j는 money[i] ~ n까지의 수이다.

money[i]를 끝에 추가하여 j를 만드는 경우의 수는 dp[j-money[i]]이므로 dp[j] 에 dp[j-money[i]]를 더해나간다.

 

money[i]를 구하는 시점에는 이미 money[i-1]까지를 사용하여 만들 수 있는 모든 경우의 수가 dp에 더해져있다.

따라서 앞의 수들을 활용하여 만들 수 있는 경우의 수에 money[i]를 끝으로 하는 경우들을 추가해주는 것이다.

또한, 만들 수 있는 수들도 money[i]에서 n으로 증가시키면서 확인하므로, money[i]가 끝에 두번 이상 들어가는 경우를 중복없이 처리할 수 있다.

 

문제에서는 n을 만들기 위한 경우의 수를 구하라고 했으므로 dp[n]을 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second 
#define MOD 1000000007

int dp[100005];

int solution(int n, vector<int> money) {
    
    dp[0] = 1;
    for (int i=0; i<(int)money.size(); i++) {
        for (int j=money[i]; j<=n; j++) {
            dp[j] += dp[j-money[i]];
            dp[j] %= MOD;
        }
    }
    
    return dp[n];
}