Coin Combinations II

https://cses.fi/problemset/task/1636/

CSES - Coin Combinations II

이 문제는 목표값을 만들기 위해 필요한 동전의 순열이 아닌 조합의 개수를 구하는 문제이다.

예를 들면,

Input:
3 9
2 3 5

Output:
3

이렇게 되어야 한다.

이 문제의 아이디어는, 목표값을 향해 1씩 숫자를 증가하면서, 모든 가능한 동전의 경우를 차례로 따져보는 것이다. 예를 들어, 위 문제를 풀기 위해서는 다음의 dp 표를 채운 뒤, dp[3][9] 값을 읽으면 된다.

i\j 0 1 2 3 4 5 6 7 8 9
0   1 0 0 0 0 0 0 0 0 0 
1   1 0 1 0 1 0 1 0 1 0 
2   1 0 1 1 1 1 2 1 2 2 
3   1 0 1 1 1 2 2 2 3 3

예를 들어, dp[1][2]의 경우를 보면, 먼저 dp[0][2]로부터 값을 가져온다음, 같은 행에서, 현재의 열 j=2 에서 동전의 배열 x의 x[0] 원소에 해당하는 값을 빼준 값에 해당하는 열(표의 범위라면)로부터 값을 가져와서 이를 더해준다. 여기서는 dp[0][2-2]가 될 것이다. 그다음 행인 dp[2][2]는 먼저 dp[1][2]로부터 값을 가져온 다음(1), 열 번호 j=2에서 동전 x[1] 원소 값인 3을 빼준 값이 유효한 열번호이면 이 값을 조회해 더해준다. OOB 가 되므로 더해줄 값이 없다. 여기까지 보면 결국, 내가 목표 숫자 2를 만들기 위해서 동전 액면 2와 3을 차례로 고려를 했고, 동전 액면 2는 고를 수 있으므로 이를 제외한 더 작은 문제로 recurse한 결과값만 더해주는 것이다. 여기서 3은 고를 수가 없었다 왜냐면 목표 숫자 2를 만들기 위해서 3은 너무 큰 값이었기 때문이다.

예를 들어 dp[1][8]도 보면, 먼저 위의 값인 0을 가져온 다음, 첫번째(1) 동전인 2를 고른 후 더 작은 문제인 dp[1][8-2] = dp[1][6]으로 recurse해 줄 수 있다. 이미 table에 그 값이 1로 존재하므로 이를 가져와 더한다 (그결과, dp[1][8]=1). 그 아랫줄인 dp[2][8]의 경우는, 위의 값인 1을 가져온 다음, dp[2][8-3] = dp[2][5] = 1 이 있으므로 그 수를 더하여, 2가 된다. 그 아랫줄인 dp[3][8]은, 윗줄에서 2를 가져온 다음, dp[3][8-5] = 1을 가져와 더하여, 3을 답으로 적는다.

// https://codeforces.com/blog/entry/70018?f0a28=1,  additionally edited.
#include <iostream>
#include <vector>
using namespace std;

int main()
{
  int mod = 1e9 + 7;
  int n, target;
  cin >> n >> target;
  vector<int> x(n);
  for (int &v : x)
    cin >> v;

  vector<vector<int> > dp(n + 1, vector<int>(target + 1, 0));
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++)
  {
    for (int j = 0; j <= target; j++)
    {
      dp[i][j] = dp[i - 1][j];
      int left = j - x[i - 1];
      if (left >= 0)
      {
        (dp[i][j] += dp[i][left]) %= mod;
      }
    }
  }
  
  // print out the dp table
  cout << 'i' << '\\' << 'j';
  for (int j = 0; j <= target; j++)
    cout << ' ' << j;
  cout << endl;
  for (int i = 0; i <= n; i++)
  {
    cout << i << ' ' << ' ' << ' ';
    for (int j = 0; j <= target; j++)
    {
      cout << dp[i][j] << ' ';
    }
    cout << endl;
  }
}

n, x = map(int, input().split())
coins = list(map(int, input().split()))
kinds = [0] * (x+1)
kinds[0] = 1
for k in range(n):
    for i in range(x+1):
        if i-coins[k] >= 0:
            kinds[i] += kinds[i-coins[k]]
        kinds[i] %= 10**9 + 7
print(kinds[-1])