[백준] 2410_2의 멱수의 합 C++

05 Dec 2023 in Study on Coding Test

LCA, 최소 공통 조상을 찾는 문제

정답제출코드

#include <iostream>

#define MOD 1000000000

using namespace std;

typedef long long ll;
ll DP[1000001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N;

    cin >> N;

    DP[1] = 1;

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

    cout << DP[N];

    return 0;
}

N=1, 2, 3, 4일 경우를 순서대로 세어보면

각각 1, 2, 4, 6이 나온다.

음.. 이번 풀이는 구글링의 도움을 받았다.

아무래도 2xN타일링 같은 문제 냄새가 나서 점화식을 세워볼까 했는데

쉽지는 않았던 것 같다.

생각해보면,

• dp[i] = i 를 2의 멱수의 합으로 나타내는 경우의 수
• dp[7] 에서 각 경우의 모든 수에 2를 곱한다면
• dp[14] 에서 모든 수가 2 이상으로 이루어진 경우의 수가 된다!
• dp[7] 에서 각 경우에 1을 더한다면
• dp[8] 에서 모든 경우에 적어도 하나 이상의 1 을 사용한 경우의 수가 된다!
• 위를 통해 [1개 이상의 1 을 사용한 경우의 수] + [2 이상만을 사용한 경우의 수] 로 나눌 수 있다!
• dp[i(짝수)] = dp[i-1] + dp[i/2]
• dp[i(홀수)] = dp[i-1]

풀이 출처 : 바로가기

난 1을 양 옆에 붙이면서 가는 것으로 생각했는데, 2를 곱하면 저렇게 될 수 있구나..

놀라울뿐..