BOJ 2410:: 2의 멱수의 합 – 다이나믹 프로그래밍

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

$n$의 제한이 1,000,000인데, $2^{19}$ < 1,000,000 < $2^{20}$이므로 1, 2, 4, …, $2^{19}$으로 $n$을 나타내는 방법의 수를 물어보는 것과 동일합니다. $m$을 아래와 같이 정의합시다.

$m[i][j]$ := 1, 2, 4, …, $2^j$으로 $i$를 나타내는 방법의 수

최종적으로 구하면 되는 건 $m[n][19]$가 됩니다.

점화식을 생각해봅시다. 1, 2, 4, …, $2^j$로 $n$을 나타낼 때 $2^j$을 전혀 안 쓸 수도 있고 적어도 한 번 쓸 수도 있습니다. 따라서 다음 관계가 성립합니다.

\[ m[i][j]=m[i][j-1]+m[i-2^j][j] \]

그런데 만약 $i$가 $2^j$보다 작으면 $2^j$을 절대 쓸 수 없으므로 이때만 $m[i][j]$ = $m[i][j-1]$이 됩니다. 또한 $i$가 0이면 방법의 수는 1가지이고 $j$가 0이면 $i$를 오로지 1 하나만을 사용해서 나타내어야 하므로 방법의 수는 역시 1가지입니다.

#include<cstdio>
 
 
using namespace std;
 
int m[1000001][20];
 
 
int main(void) {
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < 20; i++)
        m[0][i] = 1;
        
    for (int i = 1; i <= n; i++) {
        m[i][0] = 1;
        for (int j = 1; j < 20; j++) {
            if (i >= (1 << j))
                m[i][j] = (m[i][j - 1] + m[i - (1 << j)][j]) % 1000000000;
            else
                m[i][j] = m[i][j - 1];
        }
    }
 
    printf("%d", m[n][19]);
    
    return 0;
}