2410번

2410번 - 2의 멱수의 합

동전2 문제랑 완전히 똑같은 문제.

하지만 이 문제는 2의 멱수 중 하나가 1이기 때문에, 안만들어질 수 있는 경우는 없다.

따라서 그냥 초기값을 0으로 두고 풀어도 되는 문제.

문제를 풀 때 pow를 쓰거나 그냥 P배열을 만들어서 값을 사용해도 된다. (100만은 2^20 보다 작기 때문에 20이라는 숫자를 사용함)

<질문게시판>

위의 정답 코드랑 아래 코드는 개념상으로는 거의 동일하다. 위의 코드는 내림차순으로, 아래 코드는 오름차순으로 구하는데..

내 생각에는 아래 코드가 틀리다면 시간초과가 발생해야 할 것 같다. 

( 예를 들면 7을 구할 때, 위의 코드는 4 2 1 부터, 아래 코드는 1 1 1 1 1 1 1  부터 구하기 때문에)

그런데 왜 틀렸습니다 가 나오는 것일까...?

<정답 코드>

#include<iostream>
#include<string.h>
#include<math.h>
#include<vector>
using namespace std;
int P[21];
int D[1000001][30];
vector<int> v;
 
int go(int n, int before)
{
 
    if (n == 0)
    {
        return 1;
    }
    if (n < 0)
    {
        return 0;
    }
 
    if (D[n][before] > 0)
    {
        return D[n][before];
    }
 
    for (int i = 20; i>=0 ; i--)
    {
        if (i <= before && n-pow(2,i)>=0)
        {
            D[n][before] += go(n - pow(2,i), i)%1000000000;
            D[n][before] %= 1000000000;
 
        }
    }
 
    return D[n][before]%1000000000;
}
 
int main()
{
    int N;
    cin >> N;
    memset(D, 0, sizeof(D));
 
    printf("%d\n", go(N,20) % 1000000000);
 
    return 0;
}

<왤 틀리지 코드?>

#include<iostream>
#include<string.h>
#include<math.h>
#include<vector>
using namespace std;
int P[21];
int D[1000001][30];
vector<int> v;
 
int go(int n, int before)
{
 
    if (n == 0)
    {
        return 1;
    }
    if (n < 0)
    {
        return 0;
    }
 
    if (D[n][before] > 0)
    {
        return D[n][before];
    }
 
    for (int i = 0; i<=20 ; i++)
    {
        if (i >= before && n-pow(2,i)>=0)
        {
            D[n][before] += go(n - pow(2,i), i)%1000000000;
            D[n][before] %= 1000000000;
 
        }
    }
 
    return D[n][before]%1000000000;
}
 
int main()
{
    int N;
    cin >> N;
    memset(D, 0, sizeof(D));
 
    printf("%d\n", go(N,0) % 1000000000);
 
    return 0;
}