백준 2410 C++

1. 문제

문제는 다음과 같다.

 

2. 풀이법

 

문제 분류는 dp이나 적당히 수의 특성을 살펴보면 쉽게 문제를 해결할 수 있다.

 

어떤 수를 멱수의 합으로 나타낼 수 있는 방법은 두가지이다.

 

1. 그 전수에서 1(2^0)을 더한다.

 

2. 1이 아닌 멱수로만 수를 표현한다.

 

즉, 수의 합을 "1이 포함된 집합"과 "1이 포함되지 않은 집합"으로 나누는 것이다.

 

홀수의 경우, (1)으로만 풀이가 가능하다. 전 수의 멱수의 합에서 1을 더하는 것을 제외하고 다른 방법으로 합을 표현할 수 있는 방법이 존재하지 않는다.

 

짝수의 경우, 그 전수에서 1을 더하는 경우와, 그 수를 2로 나눈 값의 경우의 수를 더하면 답을 구할 수 있다.

 

해당하는 짝수를 n이라고 하자.

 

n/2를 표현하는 수가 x+y라고 했을 때, 2(x+y)는 멱수가 되므로 2의 기준이 됨을 알 수 있다.

 

자세한 이해를 위해 예시를 들자면, 

 

(base case)

 

1 = 1

2 = 1+1, 2

 

(inferred case)

3 = 1+1+1, 2+1 (2+1)

4 = 1+1+1+1, 2+1+1 (3+1)

      , 2+2, 4 (2*2)

...

 

3. 코드

 

#include 
using namespace std;

const int DIV = 1000000000;
int memo[1000001];

int main(void) {
cin.tie(0);
ios::sync_with_stdio(false);
int n; cin >> n;
memo[0] = 1;
for (int i = 1; i <= n; i++) {
i % 2 ? memo[i] = (memo[i - 1])%DIV : memo[i] = (memo[i - 1] + memo[i / 2])%DIV;
}
cout << memo[n]%DIV << "\n";
return 0;
}