BOJ 2293. 동전 1

BOJ 2293. 동전 1

랭크 : 골드5

문제 풀이

dp를 통해 k 범위에 가능한 수를 중첩해나가면 됩니다. 메모리 제한 때문에 벡터를 2개 사용해서 스왑해서 사용하고, 동전을 여러개 쓸 수 있으니 k 범위를 벗어날 때까지 하나씩 늘려서 사용하는 경우의 수를 고려해줍니다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int n, k, tmp, adding;

int main() {
    fastio;
    cin >> n >> k;
    vector<int> arr1(10001, 0);
    vector<int> arr2(10001, 0);
    arr1[0] = 1;
    for (int i=0; i < n; i++) {
        cin >> tmp;
        arr2 = arr1;
        adding = tmp;
        while (adding <= k) {
            for (int j=0; j <= k - adding; j++)
                arr2[j + adding] += arr1[j];
            adding += tmp;
        }
        swap(arr1, arr2);
    }
    cout << arr1[k] << endl;
}

알고리즘	시간복잡도	공간복잡도
dp	$O(N * k)$	$O(k)$