BOJ 2293 동전 1

문제

동전들을 조합하여 $k$원을 만드는 모든 경우의 수 계산 (순서 무관). 같은 구성의 동전은 순서가 달라도 하나로 친다.

복잡도 분석

Time: $O(n \times k) \approx 1,000,000$

Space: $O(k)$

접근법

dp[i]를 합이 i 가 되는 경우의 수로 한다.

\[dp[i] = dp[i] + dp[i - coin_value]\]

풀이

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 998244353; // or 1e9 + 7

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define all(x) (x).begin(), (x).end()

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

    vector<ll> v;
    ll n,k; cin>>n>>k;
    vector<ll> dp(k+1);
    dp[0]=1;

    rep(i,0,n){
        ll x; cin>>x;
        v.push_back(x);
    }

    for(const auto &e : v){
        rep(i,e,k+1){
            dp[i] = dp[i] + dp[i-e];
        }
    }

    // for(auto e: dp){
    //     cout << e << " ";
    // }
    cout << dp[k];

    return 0;
}

동전 루프를 밖에 오게 해서 조합을 구하도록 했다. 동전루프가 안에 가면 순열이 된다.

루프가 밖에 오면 한번 동전이 지나가면 다시 돌아오지 않는다. 모든 경우의 수는 1원.. 2원… 형태가 되어서 순서가 강제로 고정됨

동전 루프가 안에 가는 경우, 모든 금액($i$) 단계에서 모든 동전을 다시 검토합니다. 3원을 만들 때, “2원에서 1원을 더해 온 경우”와 “1원에서 2원을 더해 온 경우”를 모두 독립적으로 더합니다. 즉, 동전들이 매번 평등하게 경쟁하므로 순서가 뒤섞인 모든 경로를 다 카운트하게 됩니다. (….)

2차원 dp

• $i$: 사용할 수 있는 동전의 종류 (첫 번째 동전부터 $i$번째 동전까지 사용)
• $j$: 만들고자 하는 목표 금액

$i$번째 동전의 가치를 $v$라고 할 때, $dp[i][j]$는

\[dp[i][j] = dp[i-1][j] + dp[i][j-v]\]

1. $dp[i-1][j]$: $i$번째 동전을 단 하나도 사용하지 않고 $j$원을 만드는 경우 (이전 단계의 결과를 그대로 가져옴)
2. $dp[i][j-v]$: $i$번째 동전을 적어도 하나 사용하여 $j$원을 만드는 경우 ($j$원에서 동전 가치 $v$를 뺀 금액을 현재 사용 가능한 동전들로 만드는 경우의 수)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++) cin >> v[i];

    // dp[동전종류][금액]
    // 4MB 제한에서는 vector<vector<long long>> 사용 시 메모리 초과 발생 위험 매우 높음
    vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0));

    // 초기값: 0원을 만드는 방법은 1가지 (아무것도 안 쓰기)
    for (int i = 0; i <= n; i++) dp[i][0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            // 일단 이전 동전들로만 만드는 경우의 수를 가져옴
            dp[i][j] = dp[i - 1][j];
            
            // 현재 동전을 쓸 수 있는 금액이라면, 현재 줄의 왼쪽 값을 더함
            if (j >= v[i]) {
                dp[i][j] += dp[i][j - v[i]];
            }
        }
    }

    cout << dp[n][k] << endl;
    return 0;
}