백준 알고리즘[2410] 2의 멱수의 합 C++

문제 사이트: https://www.acmicpc.net/problem/2410

2410번: 2의 멱수의 합

문제

어떤 자연수 N을 2의 멱수의 합으로 나타내는 경우의 수를 구하는 프로그램을 작성하시오. 2의 멱수라는 것은, 2^k으로 표현되는 자연수를 의미한다.

예를 들어 7을 2의 멱수의 합으로 나타내는 경우의 수는 다음의 여섯 가지가 있다.

1. 1+1+1+1+1+1+1
2. 1+1+1+1+1+2
3. 1+1+1+2+2
4. 1+1+1+4
5. 1+2+2+2
6. 1+2+4

 

입력

첫째 줄에 N(1≤N≤1,000,000)이 주어진다.

 

출력

첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다.

 

입력 예시

7

 

출력 예시

6

 

풀이 과정 ( 시간 초과가 된 풀이 )

 

일단 7을 2의 멱급수의 합으로 나타내는 경우를 분석했다.

패턴을 좀 더 파악하기 쉽게 1의 갯수가 몇 개 쓰이는지를 기준으로 삼았다.

 

1. 1이 7개 쓰이면 0을 2의 멱급수로 만드는 경우의 수 = 1
2. 1이 6개 쓰이는 경우의 수 = 1을 2의 멱급수로 만드는 경우의 수 - 이전의 합= 1 - 1 = 0
3. 1이 5개 쓰이는 경우의 수 = 2를 2의 멱급수로 만드는 경우의 수 - 이전의 합 = 2 - 1 = 1
4. 1이 4개 쓰이는 경우의 수 = 3을 2의 멱급수로 만드는 경우의 수 - 이전의 합 = 2 - 2 = 0
5. 1이 3개 쓰이는 경우의 수 = 4를 2의 멱급수로 만드는 경우의 수 - 이전의 합 = 4 - 2 = 2
6. 1이 2개 쓰이는 경우의 수 = 5를 2의 멱급수로 만드는 경우의 수 - 이전의 합 = 4 - 4 = 0
7. 1이 1개 쓰이는 경우의 수 = 6을 2의 멱급수로 만드는 경우의 수 - 이전의 합 = 6 - 4 = 2
8. 1이 0개 쓰이는 경우의 수 = 7을 2의 멱급수로 만드는 경우의 수 - 이전의 합 = x - 6 = 0

따라서 x는 6

 

하지만 1이 쓰이는 개수가 짝수개인지 홀수개인지에 따라서 x - 4의 값이 달라질 수 있다.

위 식의 '이전의 합'을 S라고 하자

이때 x가 홀수면

x-S=0

x가 짝수면

x-S = y이다.

이때 y를 구하는 데에서 애를 먹었다...

 

이제 x가 짝수일 때 y를 구해보자 

x = 8이라 하자. 1의 개수가 0일 때 8을 구현하는 2의 멱수의 합의 경우의 수이다.

2의 멱수니까 합을 구현하는 원소들은 1, 2, 4... \(2^i\)이다.

따라서 1의 개수 0일때를 나열해보면

2+2+2+2

2+2+4

4+4

8

정도가 있다.

이것을 2로 나눠보자

그러면

1+1+1+1

1+1+2

2+2

4

이렇게 4를 2의 멱수의 합으로 나타낼 수 있게 된다.

따라서 x가 짝수 N이라면

x - S = dp[N/2]가 된다.

 

여기서 한번만 더 생각했으면 정말 이상적인 풀이가 됐을텐데 멍청하게도 그 생각을 하지 못했다.

바로 N이 짝수일 때 dp[N] = dp[N+1]라는 식이 성립하고

N에 대해서 1을 쓰지 않은 경우의 수 + 1을 한번이라도 쓴 경우의 수 = dp[N]이 된다.

식을 정리해보면

 

 

dp[N] = 1을 한번도 X + 1을 한번이라도

dp[N] = dp[N/2] + 1을 한번이라도

1을 한번이라도 썼다는 것은 dp[N-1]의 경우의 수와 동일하다. N-1은 홀수이기 때문에 1을 무조건 한 번 이상 써야한다.

즉, N이 짝수일 때

dp[N] = dp[N/2] + dp[N-1] = dp[N+1]

 

이 식을 정리하면 문제를 풀 수 있다. 하지만 난 이 방법을 N이 홀수든 짝수든 관계없이 성립하는 식을 만들고 싶은데 도저히 모르겠다...

 

사실 x-S = dp[N/2]까지만 보고 반복문으로 더럽게 풀었다.

 

풀리긴 하지만 시간초과가 된 풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long int dp[1000001];
int N;

void init() {
	//for (int i = 0; i < 1000001; i++)
		//dp[i] = -1;
	dp[0] = 1;
	dp[1] = 1;
}

int main() {
	init();
	scanf("%d", &N);
	int i;
	long long int som; // sum_of_minus

	for (int j = 1; j <= N; j++) {
		//dp[j] = ...
		som = 0;
		for (i = 0; i < j; i++) {
			long long int tmp = dp[i] - som;
			som += tmp%1000000000;
		}
		if (!((j+2) % 2))
			som += dp[j/2];
		dp[j] = som % 1000000000;
	}
	printf("%d", dp[N]);
	/*
	//dp[N] = ...
		for (i = 0; i < N; i++) {
			int tmp = dp[i] - som;
			som += tmp;
		}
		*/
}

 

가장 쉬운 풀이라고 생각되는 풀이

위에있는 코드 풀다가 시간초과되서 나열했는데 풀렸다...

0부터 2의 멱수로 표현되는 경우의 수를 쭉 나열해보자

0과 1은 1가지 경우의 수를 가지고, 2와 3은 2가지..... 

이러면 다음과 같다

1 1 2 2 4 4 6 6 10 10 14 14 20 20 ...

그리고 각각을 dp[i]라고 했을 때 짝수만을 표현하면

1 2 4 6 10 14 20이다.

짝수만 나열한 것을 dp'[i]라고 하자

이때 dp'의 차이를 나열하면

1 2 4 6 10 14 20

 1 2 2 4   4   6... 

다시 dp[i]와 비슷한 수열이 생긴다.

이러면 다음과 같은 수식을 얻을 수 있다.

dp'[i]-dp'[i-1] = dp[i]

 

다시 위에서 dp[i] = dp'[i/2]라는 것을 유도할 수 있다.

즉, dp[i] = dp'[i/2] = dp[i/2]+dp'[i/2-1]

dp'[i/2-1] = dp[i-2]

dp[i] = dp[i/2]+dp[i-2]

라는 재귀식을 얻을 수 있다.

최종 재귀식

\[\hbox{dp[i]=dp[i/2]+dp[i-2]}\]

최종 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long int dp[1000001];
int N;

void init() {
	dp[0] = 1;
	dp[1] = 1;
}

int main() {
	init();
	scanf("%d", &N);
	int i;

	for(i = 0; i <= N ; i++)
		dp[i] = (dp[i - 2] + dp[i / 2])%1000000000;
	printf("%d", dp[N]);
}