백준 2624: 동전 바꿔주기 [C/C++]

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

2624번: 동전 바꿔주기

코드

 

#include <iostream>
using namespace std;
int n, k;
int c[111], m[111];
int dp[11111]; 
int main() {
    cin >> n >> k;
    for (int i = 0; i < k; i++) cin >> c[i] >> m[i];
    dp[0] = 1;
    for (int i = 0; i < k; i++) {
        for (int j = n; j >= 0; j--) {
            if (dp[j]) {
                for (int l = 1; l <= m[i] and j + c[i] * l <= n; l++) {
                    dp[j + c[i] * l] += dp[j];
                }
            }
        }
    }
    cout << dp[n];
    return 0;
}
 

 

 

---

풀이

 

동전의 가지 수 만큼 반복한다

 

 

지폐의 금액을 역순으로 찾아간다

 

         역순으로 찾아가지 않으면, 중복으로 체크할 수 있습니다 

 

이미 나온 수라면 동전의 개수 만큼 더하기 해 준다. 

 

 

---

예시

input

10
3
5 3
10 2
1 5

 

output

3

위와 같은 입력이 있다고 가정합니다

 

1	2	3	4	5	6	7	8	9	10
0	0	0	0	1	0	0	0	0	1

동전 5원 3개만으로 나타낼 수 있는 동전의 교환 방법은 위와 같습니다

 

2.

1	2	3	4	5	6	7	8	9	10
0	0	0	0	1	0	0	0	0	2

동전 5원 3개, 10원 2개로 나타낼 수 있는 동전의 교환 방법은 위와 같습니다

 

3.

1	2	3	4	5	6	7	8	9	10
1	1	1	1	2	1	1	1	1	3

동전 1원 5개, 5원 3개, 10원 2개로 나타낼 수 있는 동전의 교환 방법은 위와 같습니다.