백준 2410번 2의 멱수의 합 C++

출처 : https://www.acmicpc.net/problem/2410

다이나믹 프로그래밍으로 해결할 수 있는 문제이다.

숫자들의 순서가 다르더라도 같은 숫자로 취급하기 때문에 오름차순으로 정렬된 숫자들만 고려하였다.

2차원 dp테이블 dp[n+1][21]을 만들었다. n+1은 입력받은 숫자가 n이기 때문에 n까지 저장할 수 있고, 21은 2^20이 약 1000000이기 때문에 저렇게 설정하였다.

 

dp[r][c]가 나타내는 값은 r의 숫자에서 2^c가 가장 마지막으로 오는 숫자들의 합의 개수라고 설정하였다.

예를 들어 4의 경우,

dp[4][0]은 2^0은 1이기 때문에 1이 마지막으로 오는 경우는 1 + 1 + 1 + 1 하나만 존재하고,

dp[4][1]은 2^1은 2이기 때문에 2가 마지막으로 오는 경우는 1 + 1 + 2 , 2 + 2 이렇게 두 개가 존재한다.

dp[4][2]는 2^2는 4이기 때문에 4가 마지막으로 오는 경우는 4 하나만 존재한다.

dp[4][3]부터는 2^3 = 8은 4를 넘어가기 때문에 계산하지 않는다.

그러므로 4를 2의 멱수의 합으로 나타내는 경우는 dp[4][0] + dp[4][1] + dp[4][2] = 4 가지이다.

 

dp테이블을 채워가는 알고리즘은 n에서 2^k(k는 0부터 증가) 를 빼가면서 처음에 설정한 오름차순의 조건에 맞게

dp[n-(2^k)][0] ~ dp[n-(2^k)][k] 의 합을 dp[n][k]에 대입시키는 것이다.

그리고 만약 n == 2^k 라면 dp[n][k]에 1을 넣는다.

예를 들어 n이 8이라고 하면, 

k=0일 때 2^0는 1이기 때문에 dp[7][?]에서 답을 찾아야 하는데, 우리는 오름차순만 취급하기로 했기 때문에 

7에서 8이 되려면 1을 더하는 방법밖에는 없고, 그 방법은 1이 마지막으로 오는 숫자들인 dp[7][0] 하나뿐이다. dp[7][0]이 1이 마지막으로 오는 경우라는 것은 위의 문단에서 설명하였다.

k=1일 때도 생각해보면 dp[6][0], dp[6][1] 두 경우를 찾을 수 있다.

k=2일 때는 dp[4][0], dp[4][1], dp[4][2] 세 경우고

k=3일 때는 8과 2^3이 같기 때문에 아예 새로운 경우이기 때문에 1을 넣어준다.

 

이런 과정을 거쳐서

dp[n-(2^k)][0] ~ dp[n-(2^k)][k] 의 합을 dp[n][k]에 대입시킨다.

그리고 만약 n == 2^k 라면 dp[n][k]에 1을 넣는다.

라는 점화식이 도출되었다.

n까지 dp테이블을 모두 채우고, dp[n][0]~dp[n][21]의 합을 구하면 답을 구할 수 있다.

 

2^k를 할 때 pow 연산을 써서 시간초과가 나서 계속 고민하다가 그냥 2를 곱하는 것으로 바꾸었더니 통과가 되었다.

pow연산이 무거운 연산인 것 같다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

const int MOD = 1000000000;

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

	int n;
	cin >> n;
	vector<vector<int>> dp(n + 1, vector<int>(21, 0));
	dp[1][0] = 1;
	for (int i = 2; i <= n; i++) {
		int tmp = 1;
		int cnt = 0;
		while (true) {
			if (i - tmp < 0) {
				break;
			}
			if (i == tmp) {
				dp[i][cnt] = 1;
				break;
			}
			int sum = 0;
			int row = i - tmp;
			for (int j = 0; j <= cnt; j++) {
				sum += dp[row][j] % MOD;
				sum %= MOD;
			}
			sum %= MOD;
			dp[i][cnt] = sum;
			tmp *= 2;
			cnt++;
		}
	}
	int ans = 0;
	for (int i = 0; i <= 20; i++) {
		ans += dp[n][i] % MOD;
		ans %= MOD;
	}
	ans %= MOD;
	cout << ans;
};