[백준 2410번] 2의 멱수의 합 (C++)

문제링크 : https://www.acmicpc.net/problem/2410

2410번: 2의 멱수의 합

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int dp[1000001];

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

    int N;
    cin >> N;

    dp[0] = dp[1] = 1;

    for(int i=2; i<=N; i++)
    {
        dp[i] = (dp[i-2] + dp[i/2])% 1000000000;
    }

    cout << dp[N] % 1000000000;

    return 0;
}

DP문제다.

경우의 수를 직접 확인하여 규칙을 찾았다.

N
1 -> 1 
2 -> 1,1 / 2
3 -> 1,1,1 / 1,2
4 -> 1,1,1,1 / 1,1,2 / 2,2 / 4
5 -> 1,1,1,1,1 / 1,1,1,2/ 1,2,2 / 1,4
6 -> 1,1,1,1,1,1 / 1,1,1,1,2 / 1,1,2,2 / 1,1,4 / 2,2,2 / 2,4
7 -> 1,1,1,1,1,1,1 / 1,1,1,1,1,2 / 1,1,1,2,2 / 1,2,2,2 / 1,1,4 / 1,2,4
.
.
.
.

1번째 : 1개
2번째 : 2개
3번째 : 2개
4번째 : 4개
5번째 : 4개
6번째 : 6개
7번째 : 6개
8번째 : 10개
9번째 : 10개
10번째 : 14개
11번째 : 14개
.
.
.
.
.

4번째 -> 2번째 or 3번째 + 2번째 or 3번째
5번째 -> 2번째 or 3번째 + 2번째 or 3번째
6번째 -> 4번째 or 5번째 + 2번째 or 3번째
7번째 -> 4번째 or 5번째 + 2번째 or 3번째
8번째 -> 6번째 or 7번째 + 4번째 or 5번째  
9번째 -> 6번째 or 7번째 + 4번쨰 or 5번째
10번째 -> 8번째 or 9번째 + 4번째 or 5번째
11번째 -> 8번째 or 9번째 + 4번쨰 or 5번째
.
.
.
.
.

위를 통해서 짝수 i번째는 i-2 or i-1 + i/2 or i/2-1 or i/2+1

홀수 i번째는 i-3 or i-2 + i/2 or i/2-1 or i/2+1 인 것을 볼 수 있다.

모두 겹치는 경우를 보면 i-2 + i/2인 것을 확인할 수 있다.