Backjoon Online Judge
"2293번 : 동전 1" 문제입니다.
문제 링크 : https://www.acmicpc.net/problem/2293
문제를 보면 바로 DP가 떠올라야 할 전형적인 DP 문제입니다.
어렵게 느껴질 수 있지만 DP의 기본 알고리즘을 이해했다면 쉽게 해결할 수 있는 문제였습니다.
k원일때 큰 숫자를 구하기 위해 k원 이하일때 숫자에서 적절한 가치를 가지는 동전을 더해주면 됩니다.
문제에서 주어진 테스트케이스처럼 k가 10이고 n이 3, 각각의 가치가 1, 2, 5일때 10원이 되기 위한 경우의 수는 아래와 같습니다.
- 9원 + (1의 가치를 지니는 동전 이용)
- 8원 + (2의 가치를 지니는 동전 이용)
- 5원 + (5의 가치를 지니는 동전 이용)
이때 9, 8, 5원은 다시 위 과정을 통해 구할 수 있습니다.
(k원이라면 1부터 k원까지 각각을 순서대로 미리 구해서 저장한다면 재귀없이 구할 수 있음. 메모이제이션 기법)
이를 활용하면 임의의 k원을 만들 수 있는 경우의 수를 구할 수 있습니다.
코드는 C++로 작성하였습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | #include <iostream> #include <memory.h> #define Max 10001 using namespace std; int main() { int n, k; int value[101]; int num[Max]; cin >> n >> k; for(int i = 0; i < n; i++) { cin >> value[i]; } memset(num, 0, sizeof(num)); num[0] = 1; for (int i = 0; i < n; i++) { for (int j = value[i]; j <= k; j++) { //k이하 합에 대해 모든 경우의 수를 구한다. num[j] += num[j - value[i]]; } } cout << num[k] << endl; } |
'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글
| 7569번 : 토마토 (0) | 2018.05.17 |
|---|---|
| 7576번 : 토마토 (0) | 2018.05.16 |
| 10844번 : 쉬운 계단 수 (0) | 2018.05.13 |
| 1005번 : ACM Craft (0) | 2018.05.12 |
| 1463번 : 1로 만들기 (0) | 2018.05.10 |