[백준] 1562번: 계단 수

문제

https://www.acmicpc.net/problem/1562

설명

비트필드를 통한 DP를 통해 해결하였다. 3차원 DP 배열을 선언한 후, 길이가 1인 경우에 대하여 초기화를 진행했다. n이 100 이하이고, 비트필드의 최댓값은 1023이므로 삼중 for문을 통해 충분히 해결 가능하다. for문을 순회하며 값이 존재하는 경우 계단 수의 마지막 수와 1씩 차이나는 새로운 계단 수의 경우에 대해 DP 배열을 초기화하였다. 만약 비트필드의 값이 1023이라면 모든 숫자를 방문한 것이다.

코드

#include <iostream>

using namespace std;

unsigned long long dp[101][10][1 << 10]; // dp[i][j][k]: 길이가 i인 계단 수의 개수, 마지막 수는 j, k는 비트필드

int main() {
	int n;
	cin >> n;

	for (int i = 1; i <= 9; i++) {
		dp[1][i][1 << i] = 1;
	}

	unsigned long long cnt = 0;
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			for (int k = 0; k < 1 << 10; k++) {
				if (dp[i - 1][j][k] != 0) {
					if (j - 1 >= 0)
						dp[i][j - 1][k | (1 << j - 1)] += dp[i - 1][j][k] % 1000000000;

					if (j + 1 <= 9)
						dp[i][j + 1][k | (1 << j + 1)] += dp[i - 1][j][k] % 1000000000;
				}
			}
		}
	}

	for (int i = 0; i <= 9; i++) {
		for (int j = 0; j < 1 << 10; j++) {
			if (j == (1 << 10) - 1) {
				cnt += dp[n][i][j];
				cnt %= 1000000000;
			}
		}
	}

	cout << cnt;
}