백준 - 계단 수 (1562) [C++]

이 문제는 비트마스킹, 다이나믹 프로그래밍을 이용해서 풀었다.

 

이 문제는 일단 계단 수를 만드는 로직을 만들고, 거기에 숫자의 여부를 포함하는 비트 필드를 추가하는 방식으로 구현하는 게 훨씬 간단하다.

또한 필드가 어떻게 구성될지는 돌릴때마다 다르므로, 바텀업 방식보다는 탑다운 방식으로 구현하는 것이 좀 더 간단하다.

 

dp[i][j][k] : i (1 <= i <= N) 번째 인덱스의 숫자를 j로 하고, 그때의 숫자 사용 필드가 flag일때의 계단 수의 수

와 같이 설정하여 문제를 풀 수 있었다.

dp배열의 크기는 최대 100 * 10 * 1024로 구성되어 약 100만이므로 충분히 2초 안에 풀 수 있다.

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

#define MOD 1000000000

int N;
int dp[101][10][1024];

int solve(int index, int present, int flag) {
	if (dp[index][present][flag] != -1) {
		return dp[index][present][flag];
	}

	if (index == 0) { // initial
		int result = 0;
		
		for (int i = 1; i <= 9; i++) {
			int flag = 0;
			flag = flag | (1 << i);
			result += solve(1, i, flag);
			result %= MOD;
		}
		
		return result;
	} else if (index == N) {
		if (flag == 1023) {
			return 1;
		} else {
			return 0;
		}
	} else {
		if (present == 0) {
			int nextFlag = flag;
			nextFlag |= (1 << 1);
			return dp[index][present][flag] = solve(index + 1, 1, nextFlag);
		} else if (present == 9) {
			int nextFlag = flag;
			nextFlag |= (1 << 8);
			return dp[index][present][flag] = solve(index + 1, 8, nextFlag);
		} else {
			int nextFlag = flag;
			nextFlag |= (1 << present - 1);
			int result = 0;
			result += solve(index + 1, present - 1, nextFlag);
			result %= MOD;

			nextFlag = flag;
			nextFlag |= (1 << present + 1);
			result += solve(index + 1, present + 1, nextFlag);
			result %= MOD;
			
			return dp[index][present][flag] = result;
		}
	}
}

void init() {
	for (int i = 0; i < 101; i++) {
		for (int j = 0; j < 10; j++) {
			for (int k = 0; k < 1024; k++) {
				dp[i][j][k] = -1;
			}
		}
	}
}

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

	cin >> N;
	init();
	int result = solve(0, 0, 0);

	cout << result << '\n';
	
	return 0;
}