백준 2293 G4 동전 1

문제: 동전 1

접근

제한 시간이 0.5초이므로, 완전 탐색으로 접근하면 안된다. 완전 탐색으로 접근시 각 동전의 종류별로 갯수를 다르게 하면서 kk를 만들 수 있는지 테스트 해야 하는데,

이건 nn개 중에 kk개를 뽑는 중복 조합의 수이고, 총 nHk=n+k−1Ck=(n+k−1)!k!(n−1)!_nH_k = _{n+k-1}C_k = \frac{(n+k-1)!}{k!(n-1)!}이므로, 아주 큰 복잡도이다.

뭔가 다른 방법을 찾아야 한다.

문제에서 관심 있는 것은 만들수 있는 방법의 가짓수이고, 실제로 kk원을 어떻게 만드는 지에는 관심이 없다.

다음의 dp 정의가 이 문제를 해결하는 데에 핵심적이다.

어떤 배열 dp를 선언하고, dp[i]를 i원을 만드는 데 사용되는 동전의 갯수라고 정의하자.

그러면 1, 2, 5원짜리 동전이 있을때, dp[i]를 다음처럼 채울 수 있다.

dp[0]은 1인데, 도합 0원을 만드려면 아무 동전도 사용하지 않는 한 가지 경우의 수가 있기 때문이다.

dp[1]의 경우, 다음 하나의 경우의 수 밖에 없다.

dp[2]의 경우, 다음의 두 경우의 수의 합이다.

dp[5]의 경우, 다음의 세 경우의 수의 합이다.

이러면 동전의 개수만큼 kk번 순회하면 되므로 복잡도는 O(nk)O(nk)이다.

이를 기반으로 코드를 짜면 아래와 같다.

코드

#include <iostream>
#include <vector>

using namespace std;

int n, k; // n in [1, 10^2] k in [1, 10^4]

vector<int> coins;
vector<int> dp;

int main() {
  cin >> n >> k;
  coins = vector<int>(n);
  for (int i = 0; i < n; ++i) {
    cin >> coins[i]; // [1, 10^5]
  }

  dp = vector<int>(k + 1, 0); // 모두 0으로 초기화
  dp[0] = 1;

  for (const int& coin_val : coins) { 
    for (int i = coin_val; i <= k; ++i) {
      dp[i] += dp[i - coin_val];
    }
  }

  cout << dp[k];

  return 0;
}

← 글 목록