백준 9084 동전

문제설명

접근방식

동전 유형의 대표적인 문제로는 그리디하게 접근해서 최소 동전 개수를 만드는 것도 있다보니 나름 친숙한 유형의 문제라서 이해는 쉽게 할 수 있었다. 다만 이번 문제는 조금 더 트릭키하게 최소나 최대의 동전 구성 유형을 묻는 것이 아니라 모든 가능한 경우의 수를 묻는 문제이다.

처음 드는 생각은 DP이긴했다. N원을 구성할 수 있는 방법이 x가지라고 가정하고 M원짜리 유형이 추가된다면 N+M원을 구성할 수 있는 방법은 x가지로 유지된다는 접근이 가능해보였다. 따라서 기본적인 문제접근은 DP의 서브문제가 중첩적으로 이용된다는 핵심 아이디어를 기반으로 가져갔다.

다만 문제가 발생할 수 있는 부분은 N원을 구성하기 위해서 N/4원짜리 동전(x) 4개가 있던 상황에서 M원 추가되는 것과 같은 경우이다. 심지어 N+M원이 x1 + My의 형식으로도 경우의 수가 발생할 수 있다보니 조금 복잡한 경우들이 발생했다.

문제에서 발생시킬 수 있는 복잡한 경우들을 나름 파악했으니 다시 전반적인 접근으로 돌아와서 보니 DP중에서도 Knapsack 방식으로 풀 수 있다는 생각이 들었다. 배낭 안에 최대한 넣을 수 있는 개수를 구하는 개념에다가 동전으로 값이 깔끔하게 나누어 떨어진다는 개념만 추가해준다면 쉽게 적응 가능해보였다.

// DP[i][j] i번째 동전까지 사용하여 j원을 구성할 수 있는 모든 경우의 수
DP[i][j] = DP[i-1][j-coin[i]]

대략 다음과 같은 아이디어까지 이끌어 낼 수 있었다. 다만 이렇게 구성해놓으면 동전의 종류가 하나인 경우에 대해서 값이 계속해서 커지는 문제가 발생해서 동전의 종류가 하나만 있는 경우에는 나누어 떨어지는 경우들로 바꾸어서 값을 처리해줬고 그리고 이전의 동전까지 사용한 경우의 수를 바탕으로 현재 추가할 수 있는 경우가 발생하게 되면 값이 업데이트 되는 방식이다보니 이차원 DP가 아닌 1차원 DP를 이중반복문으로 업데이트하는 방식을 구상했다.

// 동전의 종류 한 가지면 나누어 떨어질때로 값 업데이트
if(i == 1){
	if(j % coin[i] == 0)
        dp[j]++;
}
// 동전의 종류가 두번째 이후이면 이전에 나온 경우의 수들을 바탕으로
// 내가 들어갈 수 있는 원이면 들어가면서 값 업데이트 
else{
	if(j>=coin[i])
    	dp[j] += dp[j-coin[i]];
}

j원 coin[i]원보다 커서 여러번 중복적으로 들어갈 수 있는 경우라고 봤을 때 아래부터 하나씩 채워주면 이전의 경우의 수에 coin[i]원이 들어갈 수 있는 횟수만큼 넣어주는 개념이 된다.

ex) 6원, coin = {1, 2}

i가 1일 때의 수행결과
({1}) ({12}) ({13}) ({14}) ({15}) ({1*6})

i가 2일 때의 수행결과
({1}) => 1
({12}, {2}), ({13}, {2, 1}) => 2
({14}, {21, 12}, {22}), ({15}, {21, 13}, {22, 11}) =>3
({16}, {21, 14}, {22, 12}, {2*3}) => 4

이런 방식으로 새롭게 추가된 동전이 들어가는 횟수가 증가하게 되면 경우의 수에 차이가 발생하므로 j원에서는 j-coin[i]원의 것에서 1만 더해주면 된다.

### C++코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair <ll, ll>;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  //freopen("inp.txt", "r", stdin);
  
  int T;
  cin >> T;
  while(T--){
    int N, M;
    cin >> N;
    vector<int> coin(N+1);
    for(int i=1; i<=N; i++)
      cin >> coin[i];
    cin >> M;
    
    vector<int> dp(M+1, 0);
    dp[0] = 1;
    for(int i=1; i<=N; i++){
      for(int j=1; j<=M; j++){
        
        // 동전 종류가 하나일 경우
        // 나누어 떨어지는 경우만 1가지로 카운트
        if(i == 1){
          if(j % coin[i] == 0)
            dp[j]++;
        }
        
        // 동전 종류가 여러가지일 경우
        // 동전보다 만들어야 하는 돈의 크기가 크면
        // 기존에 만들어진 조합에 자기만 추가하면 되므로 이전값에 자기만 추가
        else{
          if(j>=coin[i])
            dp[j] += dp[j-coin[i]];
        }
      }
    }
    cout << dp[M] << '\n';
  }

}