문제 이해 단계
n가지의 동전이 있고, 그 동전에는 각각의 가치가 있다.
그리고 그 동전들을 가지고 합이 k원을 만들어야 한다.
이때 경우의 수가 총 몇 가지가 나오는지 계산하는 문제이다.
문제 접근 단계
음 일단, 늘 그렇듯 감이 오지 않으니 예제 케이스를 가지고 나열을 해보자.
여기는 K를 기준으로 K가 1~6까지 한번 해보자
1 -> 1
1+1 / 2 -> 2
1+1+1 / 2+1 -> 2
1+1+1+1 / 2+1+1 / 2+2 -> 3
1+1+1+1+1 / 2+1+1+1 / 2+2+1 / +5 -> 4
1+1+1+1+1+1 / 2+1+1+1+1 / 2+2+1+1 / 2+2+2 / 5+1 -> 5
이런 식으로의 조합이 나온다.
이를 한번 하나의 동전끼리의 관점으로 묶어보자.
일단 K가 6일 때를 살펴보자.
1일 때를 기준으로, 1원짜리 동전이 포함된 코인들을 모아보면
1+1+1+1+1+1
1+1+1+1+2
1+1+2+2
1+5
이다.
여기서 앞에 1을 제외해서 보면
1+1+1+1+1
1+1+1+2
1+2+2
5
가 되는데, 이는 K = 5 일 때의 경우의 수와 같다.
그래서 이전에 풀었던 문제처럼
모든 동전의 개수를 DP [N] = DP [N-1] + DP [N-2]...
뭐 이런 식으로 풀면 될 줄 알았다.
이전에 풀었던 문제처럼 이란 말이 무엇인지는 밑에 링크로 걸어두겠다.
그런데 이렇게 하면 2+2+2가 남는다.
이 수는 앞이 어떤 관점으로 보아도
그 자체로 어떤 계산의 부분(DP)이 되지 않는다.
즉, 해당 접근으로 풀리지 않으므로 다른 접근이 필요하다.
처음부터 돌아와서 K = 1일 때부터 동전의 관점에 생각해 보자.
동전의 관점에서 살펴본다는 것은
해당 동전은 최소한 하나는 무조건 사용한다는 뜻이다.
1원
K = 1 -> 1
K = 2 -> 1+1
K = 3 -> 1+1+1 / 1+2
K = 4 -> 1+1+1+1 / 1+1+2
K = 5 -> 1+1+1+1+1 / 1+1+1+2 / 1+2+2
K = 6 -> 1+1+1+1+1+1 / 1+1+1+1+2 / 1+1+2+2 / 1+5
2원
K = 1 -> x
K = 2 -> 2
K = 3 -> 2+1
K = 4 -> 2+1+1 / 2+2
K = 5 -> 2+1+1+1 / 2+2+1
K = 6 -> 2+1+1+1+1 / 2+2+1+1 / 2+2+2
5원
K = 1 -> x
K = 2 -> x
K = 3 -> x
K = 4 -> x
K = 5 -> 5
K = 6 -> 5+1
나열해 보면 이런 식으로 나온다.
이때 DP [K] = 가치 K원을 만들 수 있는 경우의 수라고 하자.
해당 경우에서, 현재 2원을 들고 있는 상태에서 4원을 만들어야 한다고 가정하자.
그렇다면 우리가 만들어야 하는 것은 DP [4]이다.
이미 2원을 들고 있는 상태이므로, 4를 만들기 위해서는 2원을 더 구하면 된다.
그런데 이는 우리가 이미 위해서 구해놨다.
2+1+1/2+2인데, 여기서 이미 2원은 들고 있기 때문에 2를 빼면 1+1 / 2이다.
그런데 이 것은 DP [2]와 같다.
즉 DP [4]를 구하는 데는 DP [2]의 경우에 수가 포함된다는 것이다.
여기서 한 번만 더 해보자.
1원을 들고 있는 상태에서, 4를 만들기 위해서는 3원을 더 구하면 된다.
그렇다면 위의 구했던 것 들 중에서
1+1+1+1
1+1+2
를 사용한다.
여기서 1은 미리 들고 있기 때문에
1+1+1
1+2
로만 생각해 보면 이는 DP [3]과 같다.
즉, 이로써 우리는 이렇게 식을 일반화 할 수 있다.
DP [Y] = DP [Y] + DP [Y-X]
여기서 DP [Y]를 다시 한번 더해주는 이유는
동전이 여러 가지인데, 각 경우들이 포함되는 것이기 때문이다.
예를 들어,
1원을 들 경우의 수,
2원을 들고 있을 경우의 수,
5원을 들 경우의 수가 모두 다르기 때문에 더한 것이다.
이제 이것을 코드로 구현하면 답이 된다.
문제 구현 단계
#include <iostream>
#include <algorithm>
using namespace std;
int v[101];
long d[10001];
int n, k;
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];
}
d[0] = 1;
for(int i = 1; i <=n; i++){
for(int j = v[i]; j <= k; j++){
d[j] = d[j] + d[j-v[i]];
}
}
cout << d[k];
}설명에 비해 코드는 굉장히 짧게 나온다.
우선 d [0]을 1로 초기화 한 이유는 가치가 3원짜리인 동전이 있을 경우,
K = 3일 때를 구하기 위해서이다.
3원을 이미 들고 있을 때는 0원의 동전을 줍는 것이기 때문에
가상의 동전 0원을 한 가지의 경우의 수라고 쳐주는 것이다.
밑에는 이중 반복문을 이용하였다.
동전의 가치를 기준으로 반복을 시작하여 가치에 따라 반복을 한다.
인덱스 밖으로 벗어나는 것을 방지하기 위해
시작 인덱스를 코인의 가치부터 시작하였다.
안에 코드는 아까 세웠던 점화식과 같다.
출력으로는 d [k]를 출력하여 준다.
시행착오
푸는데 이틀 걸렸던 문제이다.
정확히는 이틀 걸려서도 풀지 못해서 인터넷을 참고하였다.
처음에는 이미 풀어봤던 유형과 비슷해서
쉽게 풀 수 있을 줄 알았는데, 조금 달라서 시간이 걸리겠구나 싶었다.
두 번째는 다른 문제구나 싶었는데
그래도 방법을 알았으니 풀겠다 싶었는데, 구현이 좀 걸리네 싶었다.
세 번째는 메모리초과가 뜨니 멘탈이 나갔다.
네 번째는 아예 내 접근 자체가 잘못됐나 싶었다.
그래서 도저히 이건 아닌 것 같아서 인터넷을 찾아봤더니
내 접근 자체가 잘못된 게 맞았던 것 같다.
인터넷을 보고도 이해하는데 한참이나 걸렸던 것 같다.
이런 식으로 어떻게 접근하지?
아직도 잘 긴가민가하다. 솔직히 자신 없다.
그래도 익숙해지도록 노력해야겠다.
DP적 사고에 익숙해졌다고 생각했는데 아직 멀었다.