[c++] 동전교환

동전교환

#include<bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	//freopen("input.txt", "rt", stdin);
	int n, l, w, v, coin[13];
	vector<int> k(l+1, 0);
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> coin[i];
	}
	cin >> l;
	vector<int> dy(l+1, 1000);
	dy[0]=0;
	for(int i=0; i<n; i++){
		for(int j=coin[i]; j<=l; j++){
			dy[j] = min(dy[j], dy[j-coin[i]]+1);
		}
	}
	cout<< dy[l];
	return 0;
}

냅색 알고리즘을 사용한 문제이다.

항상 동적계획법을 사용한 문제들은 다이나믹 배열에 어떤 것들을 받아야 하는지 살펴보아야 한다.

출력하는 값이 다이나믹 배열에 오게하면 된다.

거슬러줄 금액이 1원 일 때 동전의 최소개수

거슬러줄 금액이 2원 일 때 동전의 최소개수

거슬러줄 금액이 3원 일 때 동전의 최소개수를 차례대로 동전의 종류별로 구한 후 

종류별 동전의 최소개수를 살피면서 이전에 다이나믹 배열에 들어있는 값과 비교하여 작은 값을 다이나믹 배열에 갱신해준다.