백준 2410 2의 멱수의 합

백준 2410 2의 멱수의 합

---

dp 문제 2의 멱수의 합을 풀었다. 이렇게 대놓고 dp 인 문제들은 괜찮은데, 이렇게 dp라고 생각하고 풀지 않으면 dp인지 조차 알 수 없는 문제들은 어떻게 해야할까 막막하다.

약간은 무식하게 규칙을 찾고자 써내려가보았다. 그리고 찾은 첫번째 규칙(?) 은 홀수는 생각할 필요가 없다는 것이었다. 홀수일 경우 dp 값은 1작은 짝수의 그것과 같다.

이제 계속 써내려가 보자.

    111111  11  11  11  11
    11 2 2  11  11  11  11
    11 4    11  11  11  11
    1111 2  11  11  11  11
    2 2 2   11  11  11  11
    2 4     11  11  11  11
    2 2 2 2     11  11  11
    2 2 4       11  11  11
    4 4         11  11  11
    8           11  11  11
    2 2 2 2 2       11  11
    2 2 2 4         11  11
    2 4 4           11  11
    2 8             11  11
    2 2 2 2 2 2         11
    2 2 2 2 4           11
    2 2 4 4             11
    4 4 4               11
    2 2 8               11
    4 8                 11
    2 2 2 2 2 2 2
    2 2 2 2 2 4
    2 2 2 4 4
    2 4 4 4
    2 2 2 8
    2 4 8

실제로 이렇게 써내려가면서 확인해 보았는데, 현재 n 이 짝수라면, n-2 에 1 1 이 추가 된 것에 더해, 1을 아예 사용하지 않고 2, 4, 8 .. 등만을 사용하여 나타내는 방법들이 추가되는 걸 확인할 수 있다. 여기까지를 dp로 써보면,

*dp[n] = dp[n-2] + (n을 2멱수만을 이용해 나타낸 경우들) *

이제 저 오른쪽의 경우를 어떻게 계산할 지 고민해보자.

    2 2 2 2 2 2 2
    2 2 2 2 2 4
    2 2 2 4 4
    2 4 4 4
    2 2 2 8
    2 4 8

이 부분을 2로 나누어서 써보자.

    1   1 1 1 1 1 1
    1   1 1 1 1 2
    1   1 1 2 2
    1   2 2 2
    1   2 4

아까 홀수인 경우 1이 추가 되니 홀수는 1 더 작은 짝수와 dp가 같다고 한걸 생각하면, 저 친구는

1 1 1 1 1 1
1 1 1 1 2
1 1 2 2
2 2 2
2 4

로 나타낼 수 있겠고, 저 친구는 신기하게도 dp[6] 이당 wow

그래서 dp 식을 다음처럼 세울 수 있겠다고 생각했고, 실제로 코드로 굴려보니 바로 통과되었다.

dp[n] = dp[n-2] + dp[n/2]

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

long long dp[1000002];

int main()
{
    long long n;

    cin>>n;

    dp[1]= 1;
    dp[2] = 2;
    dp[3] = 2;

    dp[4] = 4;
    dp[5] = 4;

    dp[6] = 6;
    dp[7] = 6;

    dp[8] = 10;
    dp[9] = 10;

    dp[10] = 14;
    dp[11] = 14;

    dp[12] = 20;
    dp[13] = 20;

    dp[14] = 26;
    dp[15] = 26;


    for (int i = 16; i <=n; i++)
    {
        if (i % 2 == 1)
        {
            dp[i] = dp[i-1];
        }
        else
        {
            dp[i] = (dp[i-2] + dp[i/2]) % 1000000000;
        }
    }
    cout<<dp[n];
    return 0;
}

(저렇게 dp 많이 할 필요는 전혀 없다. 내가 써보면서 하느라.. 히)

재밌는 문제였다!