해당 문제는 DP를 사용해서 푸는 문제입니다.
처음에 그리디로 문제를 접근하여서 풀려 했지만, 실패하였습니다.
그리디
동전 문제는 대부분이 그리디로 풀리기 때문에, 1,2,5로 10원을 만들기 위해서 가장 큰 동전의 경우의 수부터 고려하여서 문제를 풀려했습니다.
가장 큰 동전의 가격이 5원이므로
5원 1개, 2원 1개, 1원 3개
5원 1개, 2원 2개, 1원 1개
5원 2개
2원 1개, 1원 8개
2원 2개, 1원 6개
...
이런식으로 그리디 풀이를 하려했습니다.
하지만 이도, 구현을 하지 못해 저와 같은 생각을 한 블로그를 참고하여서 코드를 작성하였습니다.
#include <iostream>
#include <vector>
#include <utility>
#include <string.h>
#include <algorithm>
using namespace std;
int n, sum, ans;
vector<int> coin;
void recursive(int curCoinIdx, int curSum) {
curSum += coin[curCoinIdx]; //5
if (curSum == sum) ans++;
//만약 숫자가 넘어가면 다시 돌아가야함
if (curSum >= sum) {
curSum -= coin[curCoinIdx];
return;
}
int nextCoinIdx = curCoinIdx;
while (nextCoinIdx < n) {
recursive(nextCoinIdx, curSum);
nextCoinIdx++;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> sum;
for (int i = 0; i < n; i++) {
int temp = 0;
cin >> temp;
coin.push_back(temp);
}
sort(coin.begin(), coin.end(), greater<>());
for (int i = 0; i < coin.size(); i++) {
recursive(i, 0);
}
cout << ans;
}처음에 코인을 받고 가장 큰 가격의 코인부터 확인해야하므로
sort(coin.begin(), coin.end(), greater<>());정렬을 통해 coin에 5,2,1이 들어가게 하고, 재귀함수를 호출했습니다.
처음에 recursive(0,0)이 호출되면,
curSum에 5원이 들어갑니다.
nexcoidIdx에 동일하게 5원인 0이 들어가고 호출합니다.
그리고 5원을 다시 더하면 curSum이 10이됩니다.
그러고 Answer에다가 1을 추가합니다.
여기서 중요한것은 우리는 10원짜리를 5원2개를 이용해서하는 경우를 시도한것입니다.
여기서 5원을 다시 빼줘서 5원을 만들고 return을하면
for문으로 다시 돌아와서 1번째인 2원으로 만들 수 있는 경우의 수를 파악하게 됩니다.
이런식으로 재귀함수 호출을 통해서 풀려고했습니다.
그러나 여기서 문제점은 경우의 수가 2^31이라는 것입니다. 이는 애초에 연산이 2^31번 될 수 있다는 말이므로 시간내에 풀이가 불가능함을 의미합니다.
DP
그래서 답을 보고 풀었습니다.
핵심은 간단합니다.
만약 2원을 만들 수 있는 경우의 수가 4가지라고 가정해보도록 하겠습니다.
그렇다면 3원을 가지고 5원을 만들 수 있는 경우의수는 몇가지 일까요?
바로 당연히 4가지 입니다. 왜냐하면, 2원 + 3원이 5원이므로 2원의 경우의수가 바로 5원을 만들 수 있는 경우의 수 이기 때문입니다.
DP배열
0 1 2 3 4 5 6 7 8 9 10
1 0 0 0 0 0 0 0 0 0 0
0을 1로 설정한 이유는 뒤에서 설명
여기서 1원을 가지고 경우의 수를 판단해보도록 하겠습니다.
1원을 가지고 1원을 만드는 방법은 0원을 만드는 방법에서 1원을 더하는 것입니다.
고로 DP[1] = DP[0] + DP[1]임을 알 수 있습니다.
그러면 여기서 제가 처음든 고민은 아 DP0에 있는 경우의 수는 더하는것은 알겠다. 근데 기존의 DP1은 왜더하냐? 당연히 더해야합니다.
만약 Dp`[5]'= 3으로 5원을 만드는 방법이 3가지가 있다고 가정하고, 만약 5원짜리로 다시 계산하면 기존의 5원을 만드는 방법 3가지 + DP[5-5]인 DP[0]원의 경우의 수를 더해야 하기 때문입니다.
DP
0 1 2 3 4 5 6 7 8 9 10
1 1 0 0 0 0 0 0 0 0 0
DP[2]= DP[2-1] + DP[2]입니다.
DP
0 1 2 3 4 5 6 7 8 9 10
1 1 1 0 0 0 0 0 0 0 0
...
DP
0 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1 1
이 됩니다.
만약 이제 2원이 된다면
DP[2]= DP[2]+DP[2-2]가 됩니다.
이는 이미 DP[2]를 통해서 2원을 만들 수 있는 경우의수 1원 2개사용하기
+2원이 새로 들어왔으므로 2원으로 만들수 있는 경우 dp[0]의 경우의수를 합하면 됩니다.
여기서 DP[0]은 왜 1로 설정해야지를 알 수 있습니다. 그 이유는 DP[0]이 0 이라면 초기에 DP[1]을 DP[0]의 값에다 더해줘야하는데 0을 더할 수 는 없기 때문입니다.
정답코드
#include <iostream>
#include <vector>
#include <utility>
#include <string.h>
#include <algorithm>
using namespace std;
int n, sum, ans;
vector<int> coin;
int DP[10001];
int main() {
cin >> n;
cin >> sum;
for (int i = 0; i < n; i++) {
int temp = 0;
cin >> temp;
coin.push_back(temp);
}
sort(coin.begin(), coin.end());
DP[0] = 1;
for (int i = 0; i < n; i++) {
int currentCoin = coin[i];
for (int j = currentCoin; j <= sum; j++) {
DP[j] = DP[j] + DP[j - currentCoin];
}
}
cout << DP[sum];
}