여러 수를 이용해서 목표하는 숫자를 만들 수 있는 방법(Number of ways to make change)

이번 문제의 경우에는 배열안에 있는 여러 개의 숫자를 이용해서 목표하는 값을 만들 수 있는 방법 개수를 구하는 문제입니다. 

 

만약 목표하는 숫자가 6이고 이를 만드는데 사용할 수 있는 숫자가 [1, 5]라고 하면 구할 수 있는 방법 은 

 

 

1 * 6, 1 + 5

 

가 될 수 있습니다. 1을 6개를 사용하거나 1과 5를 더해서 구하는 것이죠.

 

이번 Dp가 의미하는 것은 해당 돈(인덱스)을 만들 수 있는 방법입니다. 얘를 들어서 

 

dp[1] = 1원일 때 만들 수 있는 방법 

dp[2] = 2원일 때 만들 수 있는 방법

dp[3] = 3원일 때 만들 수 있는 방법입니다. 

 

이 때 지정해준 동전을 사용해서 돈을 만들어야 하니 

 

dp[i] += dp[i-지정해준 동전]이 됩니다.

 

즉 dp[6] += dp[6-1] 1원은 한개만 사용하면 되니 5원을 이루는 방법을 더해주면 된다. 

 

아래는 코드이다.

#include <vector>
using namespace std;

int numberOfWaysToMakeChange(int n, vector<int> denoms) {
  vector<int> dp(n+1, 0);
	dp[0]=1;
	for(auto denom : denoms){
		for(int i = 1; i <= n; i++){
			if(i-denom >= 0){
				dp[i] += dp[i-denom];
			}
		}		
	}
	
  return dp[n];
}