[Algorithm]Baekjoon 2410번 :: 2의 멱수의 합

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
const int mod = 1000000000;
int n;
int dp[1000001] = { 0 };
int coins[20] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    dp[0] = 1;
    coins[0] = 1;
    
    for (int i = 1; i <= 19; ++i)
    {
        coins[i] = coins[i - 1] * 2;
    }
 
    for (int i = 0; i <= 19; ++i)
    {
        int coin = coins[i];
 
        if (coin > n) break;
 
        for (int j = coin; j <= n; ++j)
        {
            dp[j] += dp[j - coin];
            dp[j] %= mod;
        }
    }
 
    cout << dp[n];
}
 
 
 

 

이 문제는 백준의 '동전'문제랑 동일하다.

 

서로 다른 단위의 동전이 주어졌을 때(단 각 단위의동전은 무한히 쓸 수 있다),

타겟금액을 만들 수 있는 모든 경우의 수를 구하는 문제이다.

 

이 문제에서는 타겟금액을 만들때 필요한 각 수의 단위는 2의 멱수라고 되어있다.

그러면 2의 멱수가 동전의 금액단위가 되는 것이다.

타겟금액인 n은 최대 100만이니, 2^19승까지가 동전의 금액단위가 될 수 있다.

왜 19승까지냐면 20승은 100만을 넘어서니까..