[백준] Gold5 - 2410 2의 멱수의 합

백준 2410. 2의 멱수의 합

문제 설명

1이상의 양의 정수 n이 주어졌을 때, 이 수를 2^x 으로 나타낼 수 있는 수들의 합으로 표현할 수 있는 경우의 수르 구하는 문제이다. 예를들어 3이라면, {2^0 + 2^0 + 2^0, 2^0 + 2^1}로 2가지의 경우의 수를 갖는다.

주의할 점

문제 설명이 굉장히 불친절한 편이다. 예제의 경우에도 2^n 에 해당하는 수들이 포함되는지 여부를 명확히 설명해놓지 않았다. 문제에서는 2의 멱수의 합으로 표현할 수 있는 수식의 경우의 수를 구하라고 했지만 엄밀히 말하면 2 = 2^1 같은 경우는 엄밀히 말하면 대치 수식이지 합의 수식이 아니다. 정답 자체는 2^n 꼴로 나타내는 식 역시 합의 수식에 포함된다.

접근 방법

F(x) = { X | X => X를 2의 멱수의 합으로 표현한 경우들}
단 F(0) = Φ

n이 4이하인 경우에 대해 F를 구해보자.

F(1) = { 2^0 }
F(2) = { 2^0 + 2^0 , 2^1 }
F(3) = { 2^0 + 2^0 + 2^0,  2^1 + 2^0}
F(4) = { 2^0 + 2^0 + 2^0 + 2^0, 2^1 + 2^0 + 2^0, 2^2 }

여기서 잘 살펴보면, F(2)는 F(1)의 패턴에 2^0 을 더한 것 경우가 포함되어 있고 F(3) 역시 F(2)의 패턴들에 2^0 을 더한 경우가 포함되어 있다. F(4)도 마찬가지다.

이를 통해 우리는 아래와 같은 관계를 유추할 수 있다.

{X, Y | Y = {X + 2^0} X 는 F(N-1)의 구성 원소} ⊂ F(Y)

F(2) 의 예로 보면 2^0 + 2^0 이 F(1)의 2^0 에 2^0을 더한 부분 집합이다. 또한 n이 홀수인 경우 이전 경우에 2^0 을 더한 경우밖에 존재하지 않음을 알 수 있다.

F(X) = {X, Y | X = {Y + 2^0}, Y는 F(X-1)의 구성 원소 }

이제 짝수인 경우 위 부분 집합을 제외한 나머지 값들을 추려보자

F`(X) = F(X) 집합에서 F(X-1)에 2^0을 더한 수식을 제외한 경우


F`(2) = {2^1}
F`(4) = {2^1 + 2^1, 2^2}
F(5) = {2^0 x 5, 2^1 + 2^0x3, 2x2^1, 2^0 + 2^2}
F(6) = {
            2^0 x 6,
            2^1 + 4 X 2^0
            2 X 2^1 + 2 X 2^0,
            3 x 2^1
            2^2 + 2^1
       }
F`(6) = {2^1+2^1+2^1, 2^2 + 2^1}

위 수식을 잘 보면 2^0이 포함되어 있지 않고 최소 2^1 이상의 원소들로 구성됨을 알 수 있다. 이를 2^1의 곱으로 묶어보면 아래와 같다.

F`(2) = 2^1 x { 2^0 } => F(1)
F`(4) = 2^1 x { 2^0 + 2^0, 2^1} => F(2)
F`(6) = 2^1 x { 2^0 + 2^0 + 2^0, 2^1 + 2^0} => F(3)

위 수식의 우측 괄호로 묶인 집함에 해당하는 F 가 무엇인지 표기하였다. 즉 F`(N) = F(N/2) x 2^1 이 성립한다는 뜻이다.

자 여기까지 이전에 구해둔 결과가 현재의 결과를 구하는데 영향을 미치는 것이 확인 되었다. 여기서 동적 계획법을 사용할 수 있음을 알 수 있고 이를 기반으로 점화식을 다음과 같이 도출할 수 있다.

dp[i] = F(i)의 패턴의 수
dp[i] = dp[i-1] if i is odd else dp[i-1] + dp[i/2];

소스 코드

class Solution {

    int n;

    class Solution(int n) {
        this.n = n;
    }

    public void run() {
        int answer = 0;
        int[] dp = new int[n+10];
        int mod = 1000000000;
        dp[0] = 1;
        dp[1] = 1; // 2^0

        for(int i = 2 ; i <= n ; i++) {
            if( (i % 2) == 1 ) {
                dp[i] = dp[i-1];
            } else {
                dp[i] = (dp[i-1] + dp[i/2])%mod;
            }
        }

        answer = dp[n];

        System.out.println(answer);
    }
}

후기

탑다운 방식으로 풀고나서 다른 사람 풀이를 보는데 대부분 바텀업 방식으로 푼 것을 확인했다. 실제로 코드도 단순하고 점화식만 간소화 할 수 있으면 굉장히 쉽게 풀 수 있는 문제다. 다만 이걸 설명해놓은 블로그들이 제대로 이해를 하지 못한 상태로 글을 작성한 것들이 많아서 이 포스트를 작성하게 됐다. 밑도 끝도없이 점화식이 튀어나오는 식으로 글을 쓸거면 왜 쓰는건지...