문제 이해 단계
n가지의 동전이 주어지고 그 동전에는 각각의 가치가 있다.
그 동전들을 활용하여 합을 k원으로 만든다.
이때 동전을 최소한으로 사용할 때 드는 개수를 구하는 문제.
(동전은 충분히 많다는 가정)
문제 접근 단계
일단 아무런 감도 잡히지 않으니까, 예제로 어느 정도 나열을 해보자.
k = 1 ~ 15 일 때까지 쭉 나열해 보면
1 / 1 + 1 / 1 + 1 + 1 / 1 + 1 + 1 + 1
5 / 5 + 1 / 5 + 1 + 1 / 5 + 1 + 1 + 1
5 + 1 + 1 + 1 + 1 / 5 + 5 / 5 + 5 + 1
12 / 12 + 1 / 12 + 1 + 1 / 5 + 5 + 5
이런 식으로 하여 k = 15일 때, 답은 5 + 5 + 5로 3이 된다.
어느 정도 규칙이 보이기는 하는 것 같다.
어느 정도까지는 이전의 결과에 +1 한 것을 따라가다가, 더 효율적인 것이 나오면 아예 갈아 끼우는 것 같다.
1 ~ 4번을 보면 +1을 반복하다가 갑자기 5로 바뀌는 것이 그 증거이다.
그 이후에도 5 + 1 + 1... 을 반복하는 것을 보니
이전 결과가 현재 결과의 영향을 주는 것은 확실하다.
이전 결과가 현재 결과의 영향을 준다?
그렇다 이건 다이내믹 프로그래밍으로 푸는 문제라고 확신했다. 그래서 DP로 접근했다.
여기서 현재 결과에 영향을 주는 변수는 뭐가 있을까?
동전의 개수(n)는 영향을 줄까? 그렇지 않다.
동전 개수는 그냥 선택의 폭에 영향을 줄 뿐이다.
왜냐하면 DP로 구성되려면, DP [n] = DP [n-1].. 뭐 이렇게 될 텐데..
동전 3개 일 때가 동전 2개 일 때의 영향을 받는 건 상식적으로 말이 안 되지 않는가?
그렇다면 동전의 합(k)은 영향을 받을까? 그렇다 무조건 받는다.
왜냐하면 위에서 들었던 예시만 봐도,
k = 4일 때는 k = 3일 때에 +1을 한 것이고, k = 3은 k = 2 일 때의 +1을 더한 것이다.
이런 식으로 k의 값은 무조건 결과의 영향을 주고 있다.
결론은 DP를 구성할 때 k를 잘 조정하여 DP 점화식을 세워야 한다는 것이다.
한번 시뮬레이션을 돌려보자. k = 12라고 하자.
예제의 동전으로 나타낼 수 있는 합은 총 몇 가지가 있을까?
1 x 12/ 5 + 1 x 7 / 5 + 5 + 1 + 1 / 12
이렇게 총 4가지가 있다.
이 중에서 가장 경우의 수가 적은 것은 12 하나만 사용하는 것인데, 저걸 횟수의 개념으로 바꿔보자.
DP(N)를 N개일 때의 최소 코인 개수라고 한다면,
N을 합의 개념으로 보기 때문에 어떤 코인 하나를 사용하는 것을 뺀다는 개념으로 하자.
코인 하나를 사용하면 전체 k에서 그 코인 가치만큼 빠지고 횟수가 하나 올라간다.
만약 전체 합이 12인 k에서 코인가치가 5인 코인을 사용한다면
12 - 5 = 8이 남고 1번 사용한 것이 된다.
이를 수식으로 따져보면 DP(N) = 1 + DP(12-5)가 된다.
왜냐하면 우리가 구하는 12일 때의 최소 코인의 개수는
5를 빼고 남은 8개를 또 최소 횟수로 계산하여야 하기 때문이다.
이를 하는 것이 DP연산이라고 우리는 정의했고, 이는 앞서 나왔던 DP와 같은 것이다.
즉 이는 재귀함수로 구현할 수 있는 것이다.
하지만 우리는 어떤 코인을 뺀 것이 가장 최소인지 모르기 때문에
모든 코인을 사용하는 경우를 다 계산해주어야 한다.
즉, 이를 일반화하면 DP(N) = min(1 + Dp(N-(가치가 i인 코인))
n의 최대가 100이고 k의 최대가 10000이기 때문에
최악의 경우 100 * 10000 * 100 = 1억이기 때문에 1초가 넘지 않는다.
따라서 1초 안에 해결되기 때문에 가능할 것이다.
이를 코드로 구현하면 답이 나오게 된다.
문제 구현 단계
#define MAX 1000000001
long long v[10001];
long long d[10001];
int n,k;
long long Dp(int x){
for(int i = 1; i <=n; i++) if(x == v[i]) return d[x] = 1;
if(x == 0) return 0;
if(x < 0) return MAX;
if(d[x] != 0) return d[x];
long long val = MAX;
for(int i = 1; i<= n; i++){
val = min(val,1 + Dp(x-v[i]));
}
return d[x] = val;
}핵심이 되는 DP함수이다. 매개변수로 k를 뜻하는 x를 받는다.
long long으로 선언한 이유는 오버플로우를 방지하기 위해서이다.
일단 코인값과 일치하면, 곧바로 반환해 주고 x = 0 종료한다.
그리고 값이 이미 계산된 것이라면 그 값을 반환한다.
val을 가장 큰 MAX로 정의하여 오류가 나지 않도록 방지해 주고
전체 코인에 대해 재귀함수를 돌려준다.
그리고 가장 작은 값을 저장하는 것을 반복한다.
코드는 이게 끝이다.
아래는 전체코드에 대한 설명을 하고 끝내겠다.
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 1000000001
long long v[10001];
long long d[10001];
int n,k;
long long Dp(int x){
for(int i = 1; i <=n; i++) if(x == v[i]) return d[x] = 1;
if(x == 0) return 0;
if(x < 0) return MAX;
if(d[x] != 0) return d[x];
long long val = MAX;
for(int i = 1; i<= n; i++){
val = min(val,1 + Dp(x-v[i]));
}
return d[x] = val;
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> v[i];
long long ans = Dp(k);
ans = (ans >= MAX) ? -1 : ans;
cout << ans;
}Dp(k)를 ans로 지정하는데, 이 값이 MAX 즉, 존재하지 않는 값이라면 -1을 반환해 준다.
시행착오
이 문제는 나름 간단하게 풀었던 것 같다.
처음에는 감이 안 잡혀서 오래 걸릴 거 같았는데 은근 오래 안 걸렸다.
DP에 감이 잘 잡힌 것 같아서 은근히 기분이 좋다.
2차원 DP만 잘 풀었으면 좋겠다.