문제 이해 단계
Dp에서 흔히 볼 수 있는 k개의 동전으로
합이 n이 동전을 만드는 문제이다.
이 문제에서 다른 점은 동전마다 개수 제한이 있다는 점이다.
문제 접근 단계
일반적은 동전문제라면 이전에 계산해 놨던 결과 중에서
가장 많은 것을 찾는 방법을 사용한다.
하지만. 이 문제에서는 개수 제한이 있기 때문에
다른 방법을 사용한다.
가장 많은 것을 찾는 방법을 사용할 수 없는 이유는,
예제케이스에서 20과 15의 경우의 수를 구한다고 가정하자.
15원에서 5원이 사용되는 경우의 수는
(5x3), (5x2 + 1x5), (5x1 + 10x1)이다.
20원에서 5원이 사용되는 경우의 수는
(5x3 + 1x5), (5x2 + 10x1), (5x1 + 10x1 + 1x5)이다.
어떤 한 수를 더해서 20원이 될 수 있는 수는
각각의 동전을 뺀 10,15,19원밖에 없는데,
이 중 가장 경우의 수가 많은 것은 15원이다.
그런데 15원의 경우의 수 중 (5x3)은 20원을 만들 때
5원이 3개밖에 없기 때문에 사용할 수 없다.즉 이전 결괏값을 이용하는
DP와는 다른 방법을 찾아야 한다.
위에까지는 서론이었고
답을 구하는 방법을 풀이해 보겠다.
해당 문제의 조건을 읽어보면 동전의 종류는 최대 100개이고,
개수는 최대 1000개까지이다.
그렇다면 이를 정말탐색하더라도 100x1000 = 100,000이라서
1초가 넘어가지 않아서 가능하지 않을까?
싶어서 완전탐색 쪽으로 생각해 보기로 했다.
우리가 구하는 것은 경우의 수이다.
어떤 동전은 하나만 사용될 수도 있고
두 개 사용될 수도 있고 하나도 사용되지 않을 수 있다.
즉, 각각의 동전을 0개부터 전부 다 사용할 때의 경우의 수를 전부 다 탐색해 보면 된다.
이런 동작을 하는 함수를 DP로
구현하는 것이 이 문제의 답이 된다.
DP 식을 어떻게 세우면 좋을까?
DP 결과의 영향을 주는 변수를 찾아보자.
일단 확실한 건 동전의 개수는 영향을 준다.
그리고 T 그러니까 현재 지폐의 값이
얼마인지에 따라 경우의 수도 달라진다.
따라서
DP [a][b] = c : 현재 지폐 값이 a원이다. 그리고 동전을 b개 사용했을 때의 경우의 수는 c이다.
이제 이를 이용해서 모든 동전 개수 경우의 수에 따라 빼가면서
알맞은 경우의 수를 찾으면 된다.
이 DP는 메모제이션 기법을 사용하여
시간소요를 줄이기 위함이다.
자세한 것은 코드로 설명하겠다.
문제 구현 단계
pair<int,int> coins[101];
int T,k;
int d[10001][101];
int Dp(int sum,int idx){
if(sum == 0) return d[sum][idx] = 1;
if(idx > k) return d[sum][idx] = 0;
if(d[sum][idx] != -1) return d[sum][idx];
int result = 0;
for(int i = 0; i <= coins[idx].second; i++){
if(sum - (coins[idx].first*i) >= 0)
result += Dp(sum - (coins[idx].first*i),idx+1);
}
return d[sum][idx] = result;
}위에서 설명한 DP함수를 이용한 완전탐색이다.
매개변수 sum은 현재 지폐값, idx는 동전의 인덱스이다.
sum == 0 이란 뜻은 지폐값이 0원으로 딱 맞아떨어졌으므로
계산이 올바르다는 뜻이므로 1을 반환한다.
dx > k는 모든 지폐를 다 썼음에도 sum == 0 이 아니라는 뜻이므로
올바르지 않은 케이스이다.
d [sum][idx]!= -1은 그냥 내가 밑에서 모든 d배열을 -1로 초기화해서
이미 계산된 케이스는 바로바로 반환해 줘서 시간 소모를 줄였다.
반복문이 완전탐색의 핵심이다.각 코인을 0개부터 시작하여 각 코인의 최대까지 계속 반복하는데,
당연히 지폐값이 음수일 때는 계산하지 않는다.
그 계산된 값을 바로 다음 동전을
사용하는 경우의 수로 넘기는 재귀함수를 호출하여
모든 동전을 사용하는 경우의 수를 확인해 주는 것이다.
이렇게 하면 모든 동전의 경우의 수를 확인할 수 있다.
밑에는 이제 전체코드를 올리고 끝내겠다.
#include <iostream>
#include <utility>
using namespace std;
pair<int,int> coins[101];
int T,k;
int d[10001][101];
int Dp(int sum,int idx){
if(sum == 0) return d[sum][idx] = 1;
if(idx > k) return d[sum][idx] = 0;
if(d[sum][idx] != -1) return d[sum][idx];
int result = 0;
for(int i = 0; i <= coins[idx].second; i++){
if(sum - (coins[idx].first*i) >= 0)
result += Dp(sum - (coins[idx].first*i),idx+1);
}
return d[sum][idx] = result;
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> T >> k;
for(int i = 0; i < 10001; i++)
for(int j = 1; j< 101; j++) d[i][j] = -1;
for(int i = 1; i <=k; i++){
int v1,v2;
cin >> v1 >> v2;
coins[i] = make_pair(v1,v2);
}
cout << Dp(T,1);
}
시행착오
정답률이 40%가 넘어서 대중적이고 쉬운 문제라고 생각했다.
하지만 일반적인 동전문제에
개수제한이 생겨버리니까 엄청나게 어려웠다.
처음에는 위에 서론에서 이야기했던 것처럼
이전에 있던 값으로 어떻게든 해보려다가 쓴맛만 맛보고 실패했다.
완전탐색이라는 것을 파악하지도 못했는데,
왠지 파악했더라도 풀지 못했을 것 같다.
완전탐색을 해당 방식의 재귀함수로 풀어내는 것은
한 번도 해보지도 못하고 상상도 못 했다.
정말 참신했던 것 같다.
같은 골드 5문제라도 역시 난이도 편차가 있는듯하다.