[C++ / 2293] 동전 1

문제

2293번: 동전 1

---

문제 설명

n가지 종류의 동전이 있다.

각각의 동전이 나타내는 가치는 다르다.

이 동전을 사용해서, 가치의 합이 k원이 되도록 하고 싶다.

각각의 동전은 몇 개라도 사용할 수 있다.

그 경우의 수를 쓰시오.

 

! 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

---

풀이 방식

이 문제는 DP 알고리즘을 통해 푸는 문제이다.즉, 전의 결과의 값이 현재의 값을 정하는데 반영이 된다.

 

다음 예시를 통해 알아보자.

3 10
1
2
5

만약 n = 3, k= 10 이고 1, 2, 5라는 수가 주어진다.1만 사용해서 1을 만드는 경우 - 1

1만 사용해서 2을 만드는 경우 - 1

1만 사용해서 3을 만드는 경우 - 1 ....

그렇기 때문에 처음 만들어 지는 dp[j]의 값들은 전부 1이다.

1만 사용해서 0을 만들순 없지만 점화식의 편의를 위해 1로 둔다.

 

다음은 전의 결과를 기반으로 현재 값을 추가했을때 만들 수 있는 경우의 수를 모두 측정한다.

2만 사용해서는 0과 1을 만들수 없다. 그럼으로 추가가 없다.

하지만, j = 2부터는 2를 사용해서 만들 수가 있다. 

 

이때, 2를 사용해서 5를 만드는 경우의 수를 생각해 보면, 1과 2를 사용해서 3을 만드는 총 경우의 수이다.

그렇기에 j = 2부터 dp[j] 더하기가 시작되는 것이다.

 

즉 이를 정리하면 다음과 같은 식이 나온다.

dp[j] = dp[j] - dp[j - 주어진 값]

 

---

솔루션

#include <iostream>
#include <vector>

using namespace std;

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n, k;
  cin >> n >> k;

  vector<int> v(n);
  vector<int> dp(k + 1);

  for (int i = 0; i < n; i++)
    cin >> v[i];

  dp[0] = 1;

  for (int i = 0; i < n; i++)
  {
    for (int j = v[i]; j <= k; j++)
    {
      dp[j] += dp[j - v[i]];
    }
  }

  cout << dp[k] << endl;
}