특정 값을 이루는데 가장 적은 동전의 개수(Min Number Of Coins For Change)

특정 값을 이루는데 가장 적은 동전의 개수(Min Number Of Coins For Change)

 

이번에는 특정 값을 이루는데 가장 적게 사용된 동전의 개수를 구하는 문제를 풀어보겠습니다. 

 

 

만약 7의 숫자를 구성하는데 이용하는 값들이 [1, 5, 10]이 있다고 치면 만들 수 있는 방법은

 

1*7, 2 * 5등이 있을 수 있습니다. 1원의 경우 1원의 동전들을 7개 사용해야하니깐 이보다는 2원과 5원을 1개씩 사용하여 답을 구하는 방식이 훨씬 적은 동전을 사용합니다. 

 

dp의 의미는 현재 동전을 만드는데 가장 적게 사용 되는 동전의 개수입니다. 

 

dp[7] = dp[7-2] + [2];

위와 같이 dp식을 이루게 해주면 5원을 구성하는 방식, 2원을 구성하는 방식으로 문제를 해결할 수 있습니다. 

 

#include <vector>
using namespace std;

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