백준 14916 거스름돈 [C++] - 동적 계획법

문제 링크 : https://www.acmicpc.net/problem/14916

14916번: 거스름돈

#include <iostream>
using namespace std;
#define MAX 100000
#define infinity 9999999
int coin_change(int w[], int m) {
	int c[MAX] = { 0 }, i, k;
	c[1] = infinity+1;
	for (i = 2; i <= m; i++) {
		for (c[i] = infinity, k = 0; k < 2; k++) {
			if (i >= w[k] && c[i - w[k]] + 1 < c[i])
				c[i] = c[i - w[k]]+1;
		}
	}
	if (c[m] == infinity) return -1;
	return c[m];
}
int main() {
	int coin[2] = { 5,2 };
	int change_coin;
	cin >> change_coin;
	if (change_coin < 2) cout << -1;
	else
		cout << coin_change(coin, change_coin);
}

c배열은 거스름돈에 최적해를 저장하는 1차원 배열이고, w배열은 얼마짜리 동전이 있는지입니다.

c[ ] 배열에 각 거스름돈에 대해 최적해를 저장해가며 나아갑니다.

c[i] = if i>0 c[i-w[k]] +1

        if i = 0 0 

        if i<0 무한대

최소 동전 개수이기 때문에 먼저 5원짜리가 몇개 필요한지 확인한 후, 2원짜리가 몇개 필요한지 넘어갑니다.

c[1]의 값을 설정한 이유는 1원은 2원으로 거슬러 줄 수 없기 때문입니다.