[BAEKJOON] 2624 동전 바꾸기

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> using namespace std; //각 동전 당 개수가 정해져있음 //경우의 수를 구함 //중복을 방지하기 위해 큰 수부터 int main() { vector<long long>DP(10001); vector<pair<int, int>>map(101); int cost, n; scanf("%d %d", &cost, &n); DP[0] = 1; for (int j = 1; j <= n; j++) scanf("%d %d", &map[j].first, &map[j].second); for (int k = 1; k <= n; k++) { for (int j = cost; j >= 1; j--) { for (int i = 1; i <= map[k].second; i++) { if (j - map[k].first*i < 0) break; DP[j] += DP[j - map[k].first*i]; } } } printf("%lld", DP[cost]); return 0; }

큰 값 부터 시작하여

그 값을 구할 수 있는 모든 경우의 수를 구한다음

작은 값으로 넘어간다

cost가 20 동전 5짜리가 3개일때

cost가 20일때 5, 10, 15모든 경우의수를 살펴본후

cost가 19일때로 넘어간다

이후 마찬가지로 5, 10,15 모든 경우의 수를 살펴본다

이를 반복한 후

그다음 동전인 10으로 넘어간다

cost가 20일때 10, 20의 경우의 수를 모두 파악하고

이후 19일때로 반복한다

...

왜 cost가 큰 것부터 그리고 동전의 경우의 수를 모두 다 파악하는 이유는

중복을 방지하기 위해서 이다.

(동전 너무 어렵다)

+) 

2293 동전 1은

동전의 개수가 정해져 있지 않고 무한정이다

그리고 그 동전을 만들 수 있는 경우의 수를 구해주기 때문에 +1을 하지 않고 더해준다

2294 동전 2는 

동전의 개수가 정해져있지 않지만

만들수 있는 최소의 동전의 개수를 더한다

즉 +1을 해준 후 mininum을 구한다