[C++, python] BOJ, 백준 2410 - 2의 멱수의 합

문제 링크

2410번: 2의 멱수의 합

문제 풀이

이 문제는 기본 DP 문제라고 해도 될 정도로 많이 보이는 유형이다. 사람들이 정말 많이 푸는 동전 문제들과 비슷한 문제이기도 하다.

동전 1
동전 2

2293번: 동전 1

2294번: 동전 2

이 문제를 풀기 위해서는 다음과 같은 고민을 해야한다.

• 전체 문제를 부분 문제로 나눌 수 있어야한다.
• 부분으로 나눈 규칙들의 결과값은 메모리에 저장되어야 한다.
• 부분 문제에 대한 점화식을 예외없이 코드로 작성해야 한다.

위의 고민을 바탕으로 이 문제에서는 아래처럼 적용할 수 있다.

• '2의 멱수의 합이 N이 되는 경우의 수'를 전체 문제라고 한다면, '2의 멱수의 합이 i(1 <= i <= k)이 되는 경우의 수'를 구하는 부분 문제로 나눌 수 있다. 또한, '특정 멱수를 사용했을 때의 합이 i가 되는 경우의 수'를 구하는 부분 문제로 나눈다.
• 결과값은 부분 문제를 해결하며 하나의 리스트에 값을 적용시킨다.
• 입출력 예시 외의 다른 예시가 있다면 테스트를 해봐야 한다.

정답 코드

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

#define fast ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0)
#define ll long long

const int MOD = 1000000000;

int N;
vector<ll> dp(1000001, 0);
vector<ll> nums;

int main() {
	fast;
    cin >> N;
    for (int i = 1; i <= N; i <<= 1) nums.push_back(i);
    dp[0] = 1;
    for (int i = 0; i < nums.size(); i++) {
        for (int j = nums[i]; j <= N; j++) {
            dp[j] = (dp[j] + dp[j - nums[i]]) % MOD;
        }
    }
    cout << dp[N];
    return 0;
}

python

n = int(input())
lst = [1 << i for i in range(21)]
mod = 1000000000
dp = [0] * (n + 1)
dp[0] = 1
for i in lst:
    if i <= n :
        for j in range(i, n + 1):
            dp[j] += dp[j - i]
print(dp[n] % mod)