BOJ 2410번 2의 멱수의 합

BOJ : https://www.acmicpc.net/problem/2410

github : https://github.com/junho0956/Algorithm/blob/master/2410/2410/%EC%86%8C%EC%8A%A4.cpp

 

19년도 부산 코딩경시대회에 3번으로 나왔던 문제이다.

그때도 이렇게 풀었었는데 복습할겸 풀어보았다.

 

2의 멱수로 만들수있는 모든 경우의 수를 구할려면

첫 값을 현재 제곱수로 빼보느냐 안빼보느냐로 구분지어서 문제를 해결할 수 있다.

 

#include <iostream>
#include <cmath>
#include <algorithm>
#define MOD 1000000000
using namespace std;
 
int N;
int dp[1000001][20];
 
int ans(int num, int p) {
    if (num == 0) {
        return 1;
    }
    if (num < 0 || p < 0) return 0;
    if (dp[num][p]) return dp[num][p];
 
    // 현재 값에 대해 2^p 만큼 쓰거나 안쓰고 1로만 쓰거나 둘중하나
    dp[num][p] = ans(num - pow(2, p), p)%MOD + ans(num, p-1)%MOD;
    return dp[num][p];
}
 
int main() {
    cin >> N;
 
    cout << ans(N, 19) % MOD;
    return 0;
}