[백준][C++] 2410번: 2의 멱수의 합 <240>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

1. 생각의 흐름

이번 문제는 동전1 문제와 매우 유사한 문제입니다.

 

우선 DP[i] : i를 2의 멱수로 표편하는 방식의 수 라고 정의합시다.

DP[i]를 구하는 방법은 DP[i-1] + DP[i-2] + DP[i-4] + DP[i-8] + ... + DP[0] 로 구할수 있습니다.

 

예를 들어 문제의 예시인 7을 구한다 생각해봅시다.

 

2^0(1) 일때의 모든 DP 배열을 채우면 다음과 같다

1로만 각 수를 만들수 있는 경우는 전부 1가지 이다.

	i = 1	2	3	4	5	6	7
DP[i]	1	1	1	1	1	1	1

 

2^1(2) 일때의 모든 DP 배열을 채우고

이번에는 2를 사용하는 경우 인데, 1을 사용했던 경우에서 다음을 생각하면 된다.

DP[idx] = DP[idx] + DP[idx - num]

	i = 1	2	3	4	5	6	7
DP[i]	1	2	2	3	3	4	4

 

2^2(4) 일떄의 모든 DP 배열을 채우고

	i = 1	2	3	4	5	6	7
DP[i]	1	2	2	3	4	6	6

 

2^3인 8은 N보다 큰수이기 때문에 불가능 하게 되니 중단하면 됩니다.

 

 

 

 

 

 

나의 코드

#include <bits/stdc++.h>
#include <iostream>

using namespace std;
#define MAX 1000001
#define MOD 1000000000

int N;
int DP[MAX];

void find(int idx, int num) {
    if(idx > N) {
        return;
    }

    DP[idx] = (DP[idx] % MOD + DP[idx - num] % MOD) % MOD;
    find(idx+1, num);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    DP[0] = 1;
    for(int i = 1; i <= N; i = i*2) {
        find(i, i);
    }

    cout << DP[N] % MOD;

    return 0;
}