백준 2410 - 2의 멱수의 합

icpc.me/2410

 

이 문제는 DP 중에 유명한 유형인 동전 교환문제이다.

 

$2^x$의 가치를 가진 동전이 무한히 있는 것으로 생각할 수 있다.

 

dp 테이블은 다음과 같이 정의된다.

 

dp[n] = 원소들을 모두 합해서 n이 되는 집합의 갯수

 

점화식은 다음과 같이 계산한다.

 

$dp[n] += dp[n - 2^x]$

 

$n - 2^x$에서 $2^x$를 더하면 n이 되므로 이전에 계산된 $dp[n - 2^x]$를 모두 더하는 방식으로 dp[n]을 구할 수 있다.

 

전체 코드

#include <iostream>
 
#define mod 1000000000
 
using namespace std;
 
int n;
int dp[1000001];
 
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n;
    dp[0] = 1;
 
    int shft = 0;
 
    while ((1 << shft) <= n)
    {
        for (int i = 0; i <= n; ++i)
            if (i - (1 << shft) >= 0)
                dp[i] = (dp[i] + dp[i - (1 << shft)]) % mod;
        ++shft;
    }
 
    cout << dp[n];
}