백준 1562: 계단 수

문제 요약

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다.

문제 분류

• 다이나믹 프로그래밍
• 비트마스킹
• 비트필드를 이용한 다이나믹 프로그래밍

문제 풀이

비트 마스킹을 이용한 3차원 DP문제이다. 숫자를 채워나가는데 총 3개의 변수가 필요하다. 지금까지 채운 숫자의 갯수(길이)를 가리키는 pos와 마지막으로 추가한 숫자를 가리키는 last, 그리고 지금까지 채워나간 숫자의 사용 유무를 나타내는 변수 state가 필요하다. 여기서 비트 마스킹이 필요하다.

우선 1의 자리부터 1~9까지 수를 채워나가 탐색하는데(0으로 시작하면 안되므로 0은 제외), pos가 N에 도달하여 BASE CASE에 도달하였을 때, 비트 마스킹 변수 state가 111111111(2)라면 1을 반환하고, 아니라면 0을 반환한다.

DP내부에서는 last의 위아래로 숫자를 추가하여 재귀호출 하면 된다.

즉, DP[pos][state][last] = DP[pos + 1][state | 1 << (last - 1)][last - 1] + DP[pos][state | 1 << (last + 1)][last + 1]이 된다. 한 자리를 추가한다는 의미로 pos를 1 늘리고, 현재 상태에 추가할 대상(last - 1 혹은 last + 1)의 비트를 1로 갱신하고 마지막 숫자를 last - 1 혹은, last + 1로 만들면 된다.

그리고 그 결과를 1000000000의 나머지로 반환 및 출력하면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;

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

long long int sol(int state, int pos, int last) {
	if (pos == n) {
		if (state == 1023) return 1;
		return 0;
	}
	if (dp[pos][state][last] != -1) return dp[pos][state][last];
	long long int& res = dp[pos][state][last];
	res = 0;
	if(last + 1 <= 9)
		res += sol(state | (1 << last + 1), pos + 1, last + 1);
	if (last - 1 >= 0)
		res += sol(state | (1 << last - 1), pos + 1, last - 1);
	return res % 1000000000;
}

int main()
{
	long long int cnt = 0;
	scanf("%d", &n);

	memset(dp, -1, sizeof(dp));
	for (int i = 1; i < 10; i++)
		cnt += sol(1 << i, 1, i);
	cout << cnt % 1000000000;
	return 0;
}