[Baekjoon] 1562번: 계단 수

🥅 문제

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

 

🔍 설계

0~9까지의 모든 수를 포함하는 계단 수가 몇 개인지 구해야 한다.

 

길이가 n인 것이 n+1인 계단 수를 이루는 데 사용될 수 있으므로, 다이나믹 프로그래밍을 이용한다.

 

사용한 숫자를 기록하기 위해 비트마스킹을 이용한다. 9만 사용되었다면, 이진수로 1000000000인 512에 저장하는 방식이다.

 

dp[사용한 숫자][길이][마지막 숫자]로 구상한다. 다이나믹 프로그래밍이므로, 초깃값을 설정해야 하는데, 길이가 1이라면, 계단 수의 개수는 그 수만 해당되므로 1로 설정한다.

 

길이가 2 이상일 때, 0으로 끝난다면 마지막 수가 1만 되고, 9로 끝난다면 마지막 수가 8만 되고, 그 사이라면 마지막 수는 ± 1이 된다. 새로운 마지막 수를 반영하기 위해 or 연산하여 기록한다.

 

👊 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, MOD = 1e9;
long long dp[1 << 10][101][10];

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;

	if (n <= 9) {
		cout << 0 << endl;
		return 0;
	}

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

	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			for (int k = 0; k < (1 << 10); k++) {
				if (j == 0) {
					dp[k | (1 << j)][i][j] += dp[k][i - 1][j + 1] % MOD;
				}
				else if (j == 9) {
					dp[k | (1 << j)][i][j] += dp[k][i - 1][j - 1] % MOD;
				}
				else {
					dp[k | (1 << j)][i][j] += (dp[k][i - 1][j - 1] + dp[k][i - 1][j + 1]) % MOD;
				}
			}
		}
	}

	long long answer = 0;
	for (int i = 0; i <= 9; i++) {
		answer = (answer + dp[(1 << 10) - 1][n][i]) % MOD;
	}

	cout << answer << "\n";

	return 0;
}