[백준/BOJ] 3067 coins - 접근과 풀이 (c++)

https://www.acmicpc.net/problem/3067

3067번: Coins

간단한 dp문제를 풀고싶어서 찾은 문제.

---

접근 방법

 

동전의 개수가 무제한이므로, 목표금액  M원에서부터 N개의 동전 종류만큼 숫자를 빼가면서 0원이 될때까지 찾는 아주 간단한 발상? 그렇게 하면 dp[n]을 n원을 만드는 방법으로 설정할 수 있다.

 

그러나 이렇게 하니까 정답이 조금 이상했다. 왜냐하면 주어진 금액을 만족하는 동전의 조합을 구하는 것인데, 동전의 순열을 구하는 값이 나오기 때문이다.

즉 1 1 1 2원이 정답이라면 1 1 1 2 / 1 1 2 1 / 1 2 1 1 / 2 1 1 1 의 네 가지의 경우의 수를 모두 센다는 것이다. 

그래서 순서의 강제성을 부여하여, idx번째 동전을 마지막으로 사용하였고, idx번째와 같거나 낮은 종류의 동전만을 사용하여 중복을 제거하였다. dp[n][idx] : idx번째 동전까지 사용하였고, n원을 만드는 경우의 수

 

---

풀이

 

tag : dp

 

#include<iostream>
#include<string.h>
using namespace std;
int T,N,M;
int coin[21];
int dp[10001][30];
int solve(int num,int idx){
  
  if(num==0)
    return 1;
  if(num<0)
    return 0;
  int &ret = dp[num][idx];
  if(ret!=-1)
    return ret;
  ret = 0;
  for (int i = 0; i <= idx;i++){
    ret += solve(num - coin[i],i);
  }
  return ret;
}
int main(){
  cin >> T;
  while(T--){
    cin >> N;
    for (int i = 0; i < N;i++)
      cin >> coin[i];
    cin >> M;
    memset(dp, -1, sizeof(dp));

    cout << solve(M,N-1) << endl;
  }
}