문제

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

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

문제풀이

사용한 알고리즘 : DP

멱수의 합은 오름차순으로 표시되어야 한다고 생각해주었습니다.

즉, 1+1+2+4 = 1+4+2+1 = 4+1+2+1 = ... 입니다.

'dp[x][k] : 2^k 으로 끝나는 x의 멱수 합 개수' 라고 설정해주었습니다.

문제에서 N의 범위를 10^6 으로 주었으므로, 2^20 까지만 생각해주면 됩니다.

구하고자 하는 답은 dp[N][0~20]의 합일 것입니다.

( 즉, 1로 끝나는 멱수 합 개수 ~ 2^20으로 끝나는 멱수 합 개수)

오름 차순이어야 함을 생각해주면서 dp값을 채웠습니다.

예를 들어 7의 경우

dp[7][0] : 2^0 로 끝나는 7의 합 개수 = 1개

= 1+1+1+1+1+1+1

dp[7][1] : 2^1 로 끝나는 7의 합 개수 = dp[7-2^1][0] + dp[7-2^1][1]

= 2^0로 끝나는 5의 합 개수 + 2^1로 끝나는 5의 합 개수 = 1+2 = 3개

= 1+1+1+1+1+2, 1+1+1+2+2, 1+2+2+2

dp[7][2] : 2^2 로 끝나는 7의 합 개수 = dp[7-2^2][0] + dp[7-2^2][1] + dp[7-2^2][2]

= 2^0로 끝나는 3의 합 개수 + 2^1로 끝나는 3의 합 개수 + 2^2로 끝나는 3의 합 개수

= 1 + 1 + 0 = 2개

= 1+1+1+4, 1+2+4

입니다.

구하고자 하는 답은 dp[N][0] + dp[N][1] + ... + dp[N][20] 입니다.

	#include <bits/stdc++.h>
	using namespace std;
	// 오름차순 으로 더해져야 한다고 생각
	// 즉 1+2+4 = 1+4+2
	typedef long long ll;
	const ll MOD = 1000000000;
	const int MAX = 1000005;

	int N;
	// dp[x][k] : x 수, 2^k 로 끝나는 멱수의 합 개수
	int dp[MAX][22];

	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

	cin >> N;

	for (int i = 1; i <= N; ++i) {
	int k = 0;
	int curr = 1;
	while (curr <= i) {
	int pre = i - curr; // 참조하는 수
	// 기저
	if (pre == 0) dp[i][k] = 1;
	else {
	ll temp = 0LL;
	for (int j = 0; j <= k; ++j) temp = (temp + 1LL * dp[pre][j]) % MOD;

	dp[i][k] = (int)temp;
	}
	curr *= 2;
	k++;
	}
	}

	ll ans = 0LL;
	for (int i = 0; i < 22; ++i) ans = (ans + 1LL * dp[N][i]) % MOD;

	cout << ans << '\n';

	return 0;
	}

view raw BOJ 2410.cpp hosted with ❤ by GitHub