[백준 2410번] 2의 멱수의 합 풀이

2410번: 2의 멱수의 합

 

입력으로 주어진 N을 2의 멱수(2^k) 의 조합으로 몇개나 나타낼 수 있는지 구하는 문제이다. 이는 다이나믹 프로그래밍 기법으로 해결할 수 있다.

 

수를 하나씩 늘려 가능한 2^k 조합을 구해보면, 다음과 같다.

 

N=1 -> 1

N=2 -> 1+1, 2

N=3 -> 1+1+1, 2+1

N=4 -> 1+1+1+1, 2+1+1, 2+2, 4

N=5 -> 1+1+1+1+1, 2+1+1+1, 2+2+1, 4+1

...

 

N이 홀수일 경우를 살펴보면, N-1의 가능한 조합 끝에 1씩을 더해주어 완성된다.

N=3 인 경우, N=2 일 때의 조합 (1+1, 2) 의 끝에 1씩을 더하여 (1+1+1, 2+1) 이 된다.

N=5 인 경우, N=4 일 때의 조합  (1+1+1+1, 2+1+1, 2+2, 4) 의 끝에 1씩을 더하여 (1+1+1+1+1, 2+1+1+1, 2+2+1, 4+1) 이 된다.

 

N이 짝수인 경우, N-1의 가능한 조합에 1을 더해준 것과 N/2의 가능한 조합에 2를 곱해준 값을 합쳐 완성된다.

N=4 인 경우, N=3 일 때의 조합 (1+1+1, 2+1) 의 끝에 1씩 더하여 (1+1+1+1, 2+1+1) 를 만들고, N=2 일 때의 조합 (1+1, 2) 에 2를 곱하여 (2+2, 4) 를 만든다. 이 둘을 합치면 (1+1+1+1, 2+1+1, 2+2, 4) 로, N=4 일 때의 가능한 조합이 된다.

 

즉, N이 홀수일 때 가능한 2의 멱수 조합 수는 N-1의 가능한 2의 멱수 조합 수와 같고,

N이 짝수 일 때 가능한 2의 멱수 조합 수는 N-1의 가능한 2의 멱수 조합 수와 N/2의 가능한 2의 멱수 조합 수를 더하여 구해진다.

 

이를 코드로 표현하면, 

 

if (i%2) dp[i] = dp[i-1];
else dp[i] = (dp[i-1]+dp[i/2]);

 

오버플로우를 방지하기 위해 문제에서 제시한 1000000000로 나누어 준다.

 

if (i%2) dp[i] = dp[i-1];
else dp[i] = (dp[i-1]+dp[i/2])%1000000000;

 

i = N까지 dp[i] 값을 구해주고 dp[N] 을 출력하면 된다.

 

전체 코드는 다음과 같다.

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
#include <queue>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

long long dp[1000001];

int main() {

    int N;
    scanf("%d", &N);

    dp[1] = 1;
    dp[2] = 2;
    for (int i=3; i<1000001; i++) {
        if (i%2) dp[i] = dp[i-1];
        else dp[i] = (dp[i-1]+dp[i/2])%1000000000;
    }
    printf("%lld", dp[N]);
    return 0;
}