2293
백준 2293번
Link: 2293번: 동전 1
문제 설명
이 문제도 어떻게든 DP로 풀어보려 온갖 방법으로 생각해봤다.
우선 각 동전들에 대해 최대로 쓸 수 있는 갯수를 구한 다음 하나씩 빼가면서 조합을 구하려고 생각해봤다.
그런데 동전이 몇종류나 있을지도 모르고 시간도 그만큼 오래걸릴것 같아 이 생각은 접었다.
암만 고민해봐도 이 방법 말고는 떠오르는 방법이 없어 결국 답을 찾아봤다.
답 찾아보니 점화식을 세울줄 알아야 풀 수 있는 문제더라.
심지어 그 점화식을 어떻게 세우는지에 대해서도 설명이 자세하게 나와있는게 잘 없어서 한참 뒤지면서 여러개 찾아보다가 겨우 이해했다.
어떤 블로그에서 표를 그려가면서 풀면 금방 이해하고 점화식을 세울 수 있을거라 했는데, 점화식에 대해 이해하고 나니 왜 그렇게 말했는지 알 것 같다.
점화식을 구하는 과정이다.
- 1원만 쓸 때 각 금액에 대해 나올 수 있는 경우의 수
1원 2원 3원 4원 5원 6원 7원 8원 9원 10원
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
- 2원도 쓸 때 각 금액에 대해 나올 수 있는 경우의 수
1원 2원 3원 4원 5원 6원 7원 8원 9원 10원
{1, 2, 2, 3, 3, 4, 4, 5, 5, 6}
규칙
2원 경우의수 = 1원, 2원을 쓸때 0원 경우의수 + 1원만 쓸때 2원에 대한 경우의 수
3원 경우의수 = 1원, 2원을 쓸때 1원 경우의수 + 1원만 쓸때 3원에 대한 경우의 수
4원 경우의수 = 1원, 2원을 쓸때 2원 경우의수 + 1원만 쓸때 4원에 대한 경우의 수
…
1원, 2원을 쓸때 K원을 만드는 경우의 수: DP[K] += DP[K - 2]
- 5원도 쓸 때 각 금액에 대해 나올 수 있는 경우의 수
1원 2원 3원 4원 5원 6원 7원 8원 9원 10원
{1, 2, 2, 3, 4, 5, 6, 7, 8, 10}
규칙
6원 경우의수 = 1원, 2원, 5원을 쓸때 6원 경우의수 + 1원, 2원을 쓸때 6원에 대한 경우의 수
7원 경우의수 = 1원, 2원, 5원을 쓸때 7원 경우의수 + 1원, 2원을 쓸때 7원에 대한 경우의 수
…
1원, 2원, 5원을 쓸때 K원을 만드는 경우의 수: DP[K] += DP[K - 5]
최종 점화식: x원을 추가했을때 K원을 만드는 경우의 수: DP[K] += DP[K - x]
이대로 코드로 옮기면 풀린다.
작은문제로 쪼개고 그 결과를 저장하며 DP문제를 해결하는 유형에 대해서는 어떻게든 방법을 생각해낼 수 있을것 같은데, 점화식 짜서 풀어야되는 문제는 정말 답이 없는것 같다.
정답 코드
//
// Created by Keith_Lee on 10/01/2019.
//
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, K;
int main(){
cin >> N >> K;
int DP[10001] = {0, };
int coins[101];
for(int i=1; i<=N; i++){
cin >> coins[i];
}
DP[0] = 1;
for(int i=1; i<=N; i++){
for(int j=1; j<=K; j++){
if(j >= coins[i]){
DP[j] += DP[j - coins[i]];
}
}
}
cout << DP[K] << '\n';
return 0;
}