[CODEGROUND] 수강신청

목표의 수에 얼마나 가까이 도달 할 수 있는지 확인해보는 문제이다.

가장 큰 수부터 비교해보고 점점 작게 간다.

가장 작은 수를 0개를 두고 가장 큰 수까지 간 후

가장 큰 수를 1씩 더하며 비교해 보는 식으로 짰다.

즉 DP이다.

하지만 DP의 목적은 역시 memorization이지 않을까 싶다.

곰곰히 어디에다가 쓸수 있을 까 생각해보다가

내가 이미 계산해서 가능하다고 나왔던 숫자에 표시를 해놓으면 어떨까 하고 생각했다.

따라서 목표값 - 남은값의 index에 표시를 해놓고

이후 또다시 이 숫자에 접근을 한다면 이 값은 계산할 수 있다고 바로 표시해 놓는다.

뿐만 아니라 이 뜻은 숫자를 이용해서 목표한 숫자를 만들수 있다는 뜻이므로

가장 가까운 수를 더 찾아볼 필요도 없이 return 해준다.

+) 문제해결기법 : Week7 의 card문제를 활용해보았다.

#include <iostream> #include <vector> #include <fstream> #include <functional> #include <algorithm> using namespace std; int max_num, propose_num; vector<int> cache, credit; void DP(int remain, int index) { max_num = max(max_num, propose_num - remain); cache[propose_num - remain] = 1; int count = 0; if (index >= credit.size()) return; if (cache[remain]) { max_num = propose_num; return; } while (1) { if (max_num == propose_num) break; if (remain - credit[index] * count >= 0) { DP(remain - credit[index] * count, index + 1); count++; } else break; } } int main() { int for_count, credit_count; cin >> for_count; for (int i = 1; i <= for_count; i++) { cin >> credit_count >> propose_num; credit = vector<int>(credit_count, 0); cache = vector<int>(propose_num + 1, 0); for (int j = 0; j < credit_count; j++) cin >> credit[j]; sort(credit.begin(), credit.end()); max_num = 0; DP(propose_num, 0); cout << "Case #" << i << endl; cout << max_num << endl; } }