백준 2410 - 2의 멱수의 합 (C++)

 

 

N이라는 숫자를 2의 멱수 (2의 제곱수)의 합으로 표현하는 경우의 수를 구하는 문제이다.

 

문제 풀이

위의 문제는 DP를 사용하여 해결할 수 있다.

DP를 사용하기 위해선, 먼저 점화식을 세워야 한다.

 

DP배열의 i번째 인덱스의 원소는 i를 2의 멱수의 합으로 표현할 수 있는 경우의 수라고 하자.

그렇다면, DP[i]에 대한 점화식은 어떻게 될까?

 

먼저, N을 2의 멱수의 합으로 표현하기 위한 한 가지 간단한 경우가 있다.

(N - 1)을 2의 멱수의 합으로 표현한 것 뒤에 + 1을 더해주는 것이다.

 

예를 들어, 3을 2의 멱수의 합으로 표현하는 방법은 (1 + 1 + 1) 과 (1 + 2)가 있다.

이 식에 + 1만 추가해준다면, (1 + 1 + 1 + 1), (1 + 1 + 2)로 4를 2의 멱수로 표현하는 경우가 된다.

 

즉, DP[i - 1]의 값은 그대로 DP[i]에 포함된다고 할 수 있다. (모든 경우에 1만 더하면 i를 만들 수 있으므로)

 

그렇다면, DP[i] = DP[i -1]; 일까?

 

한 가지 경우를 더 고려해야 한다.

 

멱수의 합에 1이 포함되지 않은 경우이다.

2 + 4, 2 + 8, 4 + 4 등의 경우이다.

 

멱수의 합에 1이 포함되지 않았다면, 식을 이루는 모든 수가 짝수라는 의미가 된다.

즉 2로 묶을 수가 있게 된다. 2 + 4 = 2 * (1 + 2) , 2 + 8 = 2 * (1 + 4) 등등..

 

즉 N을 1을 제외한 2의 멱수의 합으로 표현하는 것은 2 * (N / 2를 멱수의 합으로 표현한 것) 이라고 할 수 있으며 이를 통해 DP[i / 2] 또한 DP[i]에 포함된다고 할 수 있다.

 

그렇다면 최종적으로 DP[i] = DP[i - 1] + DP[i / 2]라고 할 수 있다.

하지만, 이 것은 틀렸다.

 

1이 아닌 2의 멱수로만 합을 표현하는 경우 짝수의 합으로만 N을 구성하기 때문에 반드시 N은 짝수여야 한다.

즉 N이 홀수라면 DP[N / 2]를 더해선 안된다는 것이다.

 

그러므로 N이 홀수일 땐 DP[N] = DP[N -1]이 되며, N이 짝수일 땐 DP[N] = DP[N - 1] + DP[N / 2]라는 점화식이 성립한다.

 

풀이 코드

int TargetNumber = 0;
std::cin >> TargetNumber;

std::vector<int> DP(TargetNumber + 1, 0);
DP[1] = 1;
DP[2] = 2;

 

먼저, 목표 숫자를 입력받은 뒤 해당 숫자 + 1만큼 DP배열을 resize해준다.

그리고, DP[1]과 DP[2]를 1과 2로 초기화해준다.

 

for (int i = 3; i <= TargetNumber; i++)
{
    if (i % 2 == 0)
    {
        DP[i] = DP[i - 1] + DP[i / 2];
    }
    else
    {
        DP[i] = DP[i - 1];
    }

    DP[i] %= 1000000000;
}

다음은 위에 말했던 점화식을 그대로 사용하면 된다.

 

std::cout << DP[TargetNumber];
return 0;

마지막으로 목표 숫자에 해당하는 인덱스의 값을 출력해주면 된다.

 

 

코드 전문

#include <iostream>
#include <vector>
#include <cmath>
#include <set>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int TargetNumber = 0;
    std::cin >> TargetNumber;

    std::vector<int> DP(TargetNumber + 1, 0);
    DP[1] = 1;
    DP[2] = 2;

    for (int i = 3; i <= TargetNumber; i++)
    {
        if (i % 2 == 0)
        {
            DP[i] = DP[i - 1] + DP[i / 2];
        }
        else
        {
            DP[i] = DP[i - 1];
        }

        DP[i] %= 1000000000;
    }

    std::cout << DP[TargetNumber];
    return 0;
}