[Programmers] 거스름돈

• 문제
  
  정수 n을 주어진 money 배열의 값들을 이용해 구성할 수 있는 경우의 수를 구하는 문제

• 풀이
  처음에는 n이 되는 경우의 수는 n-money[i]를 모두 더한 값이라고 생각했다. 그래서 vector 하나에 값을 업데이트 하면서 답을 구했는데, 이렇게 하면 값이 중첩돼서 답이 나오지 않았다.
  ex) 5를 1, 2, 5 로 구성하는 경우
  4를 만드는 경우의 수 -> 1111, 112, 22
  3을 만드는 경우의 수 -> 12, 111
  0을 만드는 경우의 수 -> 1
  3에서 5가 되는 경우 122, 4에서 5가 되는 경우 122 => 중첩

dynamic programming의 기본은 이차원 배열을 이용하는 것이라고 한다.

특정 숫자 n을 만드는 경우의 수는
money[i] 까지 수를 모두 사용해 만드는 경우 + money[i-1]까지만 사용해 만드는 경우로 구성된다.

money[i-1]까지 사용해서 n을 만드는 경우 ->dp[i-1][n]
money[i]까지 사용해서 n을 만드는 경우 -> dp[i][j-money[i]]

처음열들을 잘 초기화하고 위의 아이디어를 사용해 문제를 해결하였다.

어려웠다.

• 코드

#include <string>
#include <vector>
#include <vector>
using namespace std;

int solution(int n, vector<int> money) {
    int answer = 0;
    int dp[money.size()][n+1];
    
    for(int i=0; i<money.size(); i++){
        for(int j=0; j<=n; j++){
            if(j==0){
                dp[i][j] = 1; 
            }
            else{
                dp[i][j] = 0;
            }
        }    
    }
    
    for(int i=0; i<money.size(); i++){
        for(int j=0; j<=n; j++){
            if(i==0&&j*money[i]<=n){
                dp[i][j*money[i]] = 1; 
            }
            else if(j>=money[i]){
                dp[i][j] = dp[i-1][j] + dp[i][j-money[i]];
            }
            else{
                dp[i][j] = dp[i-1][j];
            }
        }    
    }

    answer = dp[money.size()-1][n];
    return answer%1000000007;
}

2차원 배열을 사용하지 않고도 풀 수 있는 문제라고 한다.
참고 : https://ansohxxn.github.io/programmers/106/#-3-%EC%B0%A8-%ED%92%80%EC%9D%B4--dp