급하게임개발

https://www.acmicpc.net/problem/2294

이 문제는 dp의 기본적인 문제이다 이문제의 경우 동전의 종류 와 만들 수 있는 동전의 크기가 있다.
이문제는 내가 현재 들고있는 동전을 추가해서 현재의 가치를 만들때 최소한의 동저만 쓴경우만 선택해서 진행한다
한번 표로 봐보자

우리가 가진 동전으로 0원을 만들수 있는 경우의 수는 0 이다 만들수 없다
1원은 현재 1원하나로 만들고 5원 12원으로 만들기 위해서는 -4원 -11원 이 있어야 만들 수 있는데 해당 원수는 없으니 제외한다

자 쭉쭉 진행 되었을 때를 보자

이 상태 에서 10원을 만든다고 가정해보자 9원에서 1원을 추가해서 만드는 방법하나와 5원에서 5원을 하나 추가하는 방법이 있다 이경우 5원에서 동전 하나를 추가해서 만드는게 동전 2개이므로 5원에서 현재 5원을 선택해서 +1 해주는 방식으로 2를 넣어준다 

이문제의 점화식은

arr[i]=min(arr[i], arr[i - coin[j]] + 1);
내가 현재 선택한 동전을 추가했을 때 나올수 있는 경우의 수중 최소를 선택해주면 된다 전체 코드는 아래와 같다

#include <iostream>
#include <algorithm>
using namespace std;
#define INF 987654321
int n, k;
int coin[100];
int arr[10000] = { 0, };
int main() {
	cin >> n >> k;
	for(int i=0;i<n; i++){
		cin >> coin[i];
	}
	for (int i = 1; i <= k; i++) {
		arr[i] = INF;
		for (int j = 0; j < n; j++) {
			if (i - coin[j] >= 0) {
				arr[i]=min(arr[i], arr[i - coin[j]] + 1);
			}
		}
	}
	if (arr[k]==INF)
		cout << -1;
	else
		cout << arr[k];
}