백준 4190(Exact Change)

www.acmicpc.net/problem/4190

4190번: Exact Change

진짜 한 스무번 제출한 문제

 

dp문제인데 이것 역시 나한테 엄청 도움이 되었던 문제인것 같다. 

정해져 있는 금액이고, (0~MAX)

그 금액에 해당하는 최소 화폐갯수를 하나하나 채워나간다. 

 

만약에 총 금액이 정해져 있지 않으면 불가능하다 -> 2^N의 반복이 필요하다.

 

일단 그러면 핵심은 

금액의 범위가 정해져있어서, 하나씩 원래 있던 곳에 넣다보면 (N*금액범위)

 

문제에서 원하는 dp가 완성된다.

 

그리고 주의할 점은 하나의 화폐는 한번만 써야한다. 사실 이건 당연한데 

다른 코드를 참조하다가 이것을 계속 빠뜨려서 15번은 WA가 나온듯하다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAX 100000

int T, D, N;

int main() {
	cin >> T;
	while (T--) {
		cin >> D >> N;
		vector<int> coin(N);
		for (int i = 0; i < N; i++) {
			cin >> coin[i];
		}
		int dp[MAX + 1];
		memset(dp, 0, sizeof(dp));
		for (int i = 0; i < N; i++) {
			for (int j = 10000; j >= 0; j--) {
				if (dp[j]==0) continue;
				if (dp[j + coin[i]]) {
					dp[j + coin[i]] = min(dp[j + coin[i]], dp[j] + 1);
				}
				else {
					dp[j + coin[i]] = dp[j] + 1;
				}
			}
			if (dp[coin[i]] == 0)dp[coin[i]] = 1;
		}
		for (int i = D; i <= MAX; i++) {
			if (dp[i]) {
				cout << i << " " << dp[i] << "\n";
				break;
			}
		}

	}
}