[BAEKJOON] 2294 동전2

이문제는 못풀었다..어려웠다..

정답을 보고 사람들은 천재라고 생각했다.. 신박한 방법..

일단 처음에는 DP의 완전 기본적인 구조를 이용했다.

그 합을 만드는 데 얼마나 작은 수가 필요한지 minimum을 저장했다.

그리고 이후 그 minimum을 구한 적이 있으면 return하면서 풀었다.

아 그리고 1부터 0개씩 써가면서 모든 수를 다 돌아보는 형식이다.

시간이 오래 걸릴 만 했다..ㅎㅎ

충분히 시간을 줄일 수 을 꺼라 생각했는데 코드로 어떻게 짜야하는지 몰랐다.

첫번째(오답)

#include <iostream> #include <vector> #include <fstream> #include <algorithm> using namespace std; #define MAX 1e6 int sum_coin_count, sum_coin; vector<int> coin; vector<long long> cache; long long make_coin(int index, int remain_coin) { if (remain_coin == 0) return 0; if (remain_coin < 0 || index >= sum_coin_count) return MAX; long long&ret = cache[remain_coin]; if (ret != MAX) return ret; for (int func_coin_index = 0; func_coin_index <= (sum_coin / coin[index]); func_coin_index++) ret = min(ret, make_coin(index + 1, remain_coin - (coin[index] * func_coin_index)) + func_coin_index); return ret; } int main() { ifstream fcin; fcin.open("2294_input.txt"); fcin >> sum_coin_count >> sum_coin; coin = vector<int>(sum_coin_count); cache = vector<long long>(sum_coin + 1, MAX); for (int j = 0; j < sum_coin_count; j++) fcin >> coin[j]; cout << make_coin(0, sum_coin) << endl; for (int j = 0; j <= sum_coin; j++) cout << j << "번째 : " << cache[j] << endl; system("pause"); }

와 근데 이런 정답을 발견했다 진짜 천재라고 생각했다.

일단 들어온 동전의 가격을 가장 작은 것부터 시작해서 큰 것까지 정렬해준다.

그리고 작은 것부터 그 수를 만들때 얼마나 많은 수가 필요한지 저장해둔다.

왜 cache[coin[j]]=1을 두고 시작하냐하면 coin[j]을 만들 수 있는 방법은 1개이기 때문이다.

그 다음 큰것으로 넘어가고 이렇게 반복하다보면 마지막 원하는 목표값을 만드는 최소값을 구할 수 있다.

기억해두자 동전의 개수를 최소로 쓰는 법!

두번째(정답)

#include <iostream> #include <vector> #include <algorithm> #include <functional> #include <fstream> using namespace std; #define MAX 987654321 int main() { int coin_count, goal_coin; cin >> coin_count >> goal_coin; vector<int> coin = vector<int>(coin_count); vector<int> cache = vector<int>(100001, MAX); for (int j = 0; j < coin_count; j++) cin >> coin[j]; sort(coin.begin(), coin.end()); for (int j = 0; j < coin_count; j++) { cache[coin[j]] = 1; for (int k = coin[j] + 1; k <= goal_coin; k++) cache[k] = min(cache[k], cache[k - coin[j]] + 1); } if (cache[goal_coin] == MAX) cout << -1 << endl; else cout << cache[goal_coin] << endl; }