[알고리즘/C++] 최소 지폐 개수 구하기(동적 프로그래밍)

각 가치가 A, B, C, D인 화폐가 있다고 하자. 최소한의 화폐 장수를 사용하여 특정 액수 X를 만들어야 하는 문제이다. 

 

최적해의 해를 빠르게 구하기 위해서는 동적 프로그래밍(Dynamic Programming)을 이용하여야 한다. 

 

typedef vector<int> vi;
#define inf pow(2,30);

int minNumCoin(int curBalance, vi coinCase, map<int, int>& selected) {
	if (curBalance < 0) {
		return inf;
	}
	else if (curBalance == 0) {
		return 0;
	}
	else {
		int ans = inf;
		for (auto coin : coinCase){
			int pre_result = minNumCoin(curBalance - coin, coinCase, dp, dpVal, selected);
			int temp = ans;
			ans = min(ans,  pre_result + 1);
			if (ans != temp) {
				//마지막 업데이트를 찾아서
				selected[curBalance] = coin;
			}
		}
		return ans;
	}
}

동적 프로그래밍을 재귀함수를 이용하여 구현한 코드이다. 

 

	if (curBalance < 0) {
		return inf;
	}
	else if (curBalance == 0) {
		return 0;
	}

먼저 만나는 조건이 인수로 받아들인 curBalance가 음수일 경우 아주 큰 수를 반환한다. 

 

음수를 만들어내는 화폐 총합이 불가능하기 때문이다. 

 

그리고 0을 만들어내는 경우의 수는 0이다. 

 

	else {
		int ans = inf;
		for (auto coin : coinCase){
			int pre_result = minNumCoin(curBalance - coin, coinCase, selected);
			int temp = ans;
			ans = min(ans,  pre_result + 1);
			if (ans != temp) {
				//마지막 업데이트를 찾아서
				selected[curBalance] = coin;
			}
		}

ans를 현재 단계의 잔액(curBalance)에서의 답으로 할 때, 먼저 아주 큰 수로 설정한다. 

 

그리고 화폐의 모든 Case를 순회하면서 현재의 잔액(curBalance)에서 각 케이스의 화폐를 뺀 금액을 새로운 인자로서

 

재귀함수를 호출한다. 재귀 함수가 계속 호출되면서 첫 번째 인수(curBalance)가 음수 혹은 0에 도달하는데 

 

음수는 아주 큰 수를 반환하고 0일 때는 0을 반환한다. 가장 밑에서부터 살펴보면 점점 잔액을 키워나가면서 

 

이전 재귀함수의 값과 비교해나가면서 최소 경우의 수를 갱신해간다. 

 

우리가 구하고자 하는 답은 화폐의 최소 장수이기 때문에 이전 재귀함수의 반환 값(pre_result)에 1을 더한 값과 현재의 

 

ans를 비교하는 것을 볼 수 있다. selected는 현재 잔액을 달성하기 위해 마지막으로 선택된 화폐 케이스(coinCase)를 

 

저장하는데, 어떤 화폐들로 잔액을 구성한 것인지 살펴보기 위해 만들어졌다. 

 

화폐 케이스(coinCase)를 순회하면서 결국 ans에는 현재의 curBalance를 구성하는 최소 장수의 화폐 개수가 담긴다. 

 

하지만 재귀함수는 매우 느리기 때문에 메모화(Memorization)이라는 개념을 도입하여 실행시간을 단축할 수 있다. 

 

이것을 메모화 재귀라고 한다. 

 

int minNumCoin(int curBalance, vi coinCase, map<int, bool>& dp, map<int, int>& dpVal, map<int, int>& selected) {
	if (curBalance < 0) {
		return inf;
	}
	else if (curBalance == 0) {
		return 0;
	}
	else {
		if (dp[curBalance]) {
			return dpVal[curBalance];
		}
		int ans = inf;
		for (auto coin : coinCase){
			int pre_result = minNumCoin(curBalance - coin, coinCase, dp, dpVal, selected);
			int temp = ans;
			ans = min(ans,  pre_result + 1);
			if (ans != temp) {
				//마지막 업데이트를 찾아서
				selected[curBalance] = coin;
			}
		}
		dp[curBalance] = true;
		dpVal[curBalance] = ans;
		return ans;
	}
}

 

dp에 현재 잔액(curBalance)에서의 최소 화폐 장수 정보가 이미 구해졌다면, 이를 바로 반환한다. 

 

int main() {
	vi coinCase = { 1, 3, 5, 7, 10};
	int moneySum = 29;
	map<int, bool> dp;
	map<int, int> dpVal;
	map<int, int> selected;
	int minCoin = minNumCoin(moneySum, coinCase,dp ,dpVal, selected);
	cout << "(recur)필요 최소 코인의 수: " << minCoin << "\n";

	cout << "used coins: ";
	while (moneySum > 0) {
		cout << selected[moneySum] << " ";
		moneySum -= selected[moneySum];
	}
}

(recur)필요 최소 코인의 수: 4
used coins: 5 7 7 10

동적 프로그래밍을 재귀함수로 이용하지 않고 반복문을 이용해서 구성할 수도 있다. 

 

반복문을 이용한 버전이 더 빠르게 구동한다.

int minNumCoin_iter(int curBalance, vi coinCase, map<int, int>&ans ,map<int, int>& selected) {

	ans[0] = 0;
	for (int cur = 1; cur <= curBalance; cur++) {
		ans[cur] = inf;
		for (auto coin : coinCase) {
			if (cur - coin >= 0) {
				int temp = ans[cur];
				ans[cur] = min(ans[cur], ans[cur - coin] + 1);
				if (temp != ans[cur]) {
					selected[cur] = coin;
				}
			}
		}
	}
	return ans[curBalance];
}