[C/C++] 백준 #2410 2의 멱수의 합(동적 계획법)

#2410 문제는 점화식을 잘 세우면 동적 계획법을 이용해서 풀 수 있습니다.

 

 

하지만 늘 그렇듯이 점화식을 만드는 과정이 쉽지만은 않습니다.

 

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

2410번: 2의 멱수의 합

 

어떤 수가 주어지면, 그 수를 2의 멱승(1, 2, 4, 8, ...과 같이 \(2^k\)으로 표현되는 수)의 합으로 표시하는 경우의 수를 구하는 것입니다.  2의 멱승을 하니 조금 이상할 수 있지만, 이진수 표현법이 기초가 됩니다.

 

홀수가 주어졌다고 하죠.  예를 들면 9가 주어졌습니다.

 

8 + 1

4 + 4 + 1

4 + 2 + 2 + 1

4 + 2 + 1 + 1 + 1

4 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 2 + 1

2 + 2 + 2 + 1 + 1 + 1

2 + 2 + 1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 + 1  + 1 + 1

1 + 1 + 1 + 1 + 1 + 1 + 1  + 1  + 1

 

여기서 눈여겨 볼 것은 항상 +1은 따라 다닌 다는 것이죠.  10가지 모두에 공통된 +1을 제거하면 9의 경우의 수와 8의 경우의 수는 같다는 것입니다.  여기서 우리는 하나의 법칙을 발견할 수 있습니다.

 

\[ D_{2k+1} = D_{2k} \]

 

짝수인 경우를 생각해보도록 합니다.  8이라고 한다면, 두가지로 나누어서 생각토록 합니다.

8

4 + 4

4 + 2 + 2

2 + 2 + 2 + 2

이와 같이 1을 사용하지 않은 경우입니다.  실제 이 숫자들은 4를 만드는 경우를 곱하기 2한 것과 같습니다.

다음으로는 7을 만드는 경우입니다.

4 + 2 + 1

4 + 1 + 1 + 1

2 + 2 + 2 + 1

2 + 2 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 + 1

1 + 1 + 1 + 1 + 1 + 1 + 1

여기에 1을 더하면 8을 만들 수 있습니다.  이렇게 하면 다음과 같은 점화식을 얻을 수 있습니다.

\[ D_{2k} = D_{2k-1} + D_{k} \]

 

그래서 정리하면 다음과 같습니다.

\[ D_{1} = 1 \]

\[ D_{2k} = D_{2k-1} + D_{k} = D_{2(k-1)} + D_{k}\]

\[ D_{2k+1} = D_{2k} \]

 

이 식을 홀수는 항상 -1을 한 짝수와 같으므로 2로 나누어서 정리할 수 있습니다.

그래서 변형된 형태는 다음과 같습니다.

\[ D'_{0} = 1 \]

\[ D'_{k} = D'_{k-1} + D'_{\lfloor k/2 \rfloor} \]

 

제가 작성한 소스입니다.  소스는 동적 계획법을 재귀함수를 이용해서 풀었습니다.  사실 이 방법이 좋은 것은 아닙니다.  왜냐하면 항상 전항을 검사하기 때문에 효율이 좋지 않습니다.

//------------------------------------------------
//    baekjoon #2410
//        - by Aubrey Choi
//        - created at 2019-08-07
//------------------------------------------------
#include <stdio.h>
#define    MOD    1000000000

//    a(2m+1) = a(2m), a(2m) = a(2m-1) + a(m)
long long dp[500001] = { 1, 2, 4, 6 };
long long bpart(int n)
{
    if(dp[n]) return dp[n];
    return dp[n] = (bpart(n-1)+bpart(n>>1))%MOD;
}

int main()
{
    int n;
    scanf("%d",&n);
    printf("%lld\n", bpart(n>>1));
    return 0;
}