<DP> BOJ 2410 2의 멱수의 합

문제

자연수 N을 2의 멱수의 합으로 나타내는 경우의 수를 구하라.

• 1 <= N <= 1000000

접근

• 1. $d[N][M]$을 $2^M$까지 포함 가능하여 N을 만들 수 있는 경우의 수로 정의합니다. 그리고 다음과 같은 점화식을 세워 봅니다.
     $d[N][M] = \sum_{j=0}^{M} d[N-2^j][j]$
• 2. 그런데 위와 같은 점화식을 사용하면 시간 복잡도가 배열의 수 X 한 원소를 구하기 위한 호출 횟수에 의해 $O(NM^2)$이 되어 문제 시간 제한에 적합하지 않습니다.
• 3. 호출 횟수를 줄이기 위해 점화식을 바꿔봅니다. $d[N][M]$을 만들기 위해 두가지 경우의 수로만 나누어주면 됩니다. $2^M$을 꼭 포함해서 만드는 경우와 절대 포함하지 않는 경우로 나누어주면 한 원소당 2번만 호출합니다.

  • $2^M$을 포함하는 경우
    $d[N-2^M][M]$와 동일합니다. 왜냐하면 $d[N-2^M][M]$을 구하는데 $2^M$이 사용됐건 안됐건 $2^M$을 더해줄 것이기 때문입니다.

  • $2^M$을 포함하지 않는 경우
    $d[N][M-1]$이 됩니다. $2^M$은 절대 사용하지 않고 N을 만든 경우의 수 입니다.

• 4. 중요 포인트는 문제를 잘게 자르되 두 가지 경우로만 나누어 호출 횟수를 매우 줄였다는 점입니다.

JAVA 코드

import java.io.*;
import java.util.*;

class baek__2410 {
    static int MAX = 1000000;
    static long r = 1000000000;
    static long[][] d = new long[MAX + 1][21];

    static long go(int n, int m) {
        if (m < 0)
            return 0;
        if (n <= 0) {
            if (n == 0)
                return 1;
            return 0;
        }

        if (d[n][m] != -1)
            return d[n][m];

        d[n][m] = go(n - (1 << m), m) + go(n, m - 1);
        d[n][m] %= r;

        return d[n][m];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for (int i = 0; i < MAX + 1; i++) {
            for (int j = 0; j < 21; j++) {
                d[i][j] = -1;
            }
        }

        int n = Integer.parseInt(br.readLine());

        System.out.print(go(n, 20));
    }
}