[2410] 2의 멱수의 합

https://www.acmicpc.net/problem/2410

2410번: 2의 멱수의 합

<문제>

1'000'000 이하의 2의 멱수를 전부 전처리해두고, 배낭문제와 비슷한 방식으로 풀 수 있다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, dp[1000001], base[20];
const int M = 1000000000;
int main(void) {
    cin >> n;
    base[0] = 1;
    int i, j;
    for (i = 1;; i++) {
        if (base[i - 1] * 2 > 1000000) break;
        base[i] = base[i - 1] * 2;
    }
    dp[0] = 1;
    for (i = 0; i < 20; i++) {
        if (base[i] > n) break;
        for (j = base[i]; j <= n; j++) {
            dp[j] += dp[j - base[i]];
            dp[j] %= M;
        }
    }
    cout << dp[n];
    return 0;
}