백준) 1562 계단

1562. 계단 수

문제

45656이란 수를 보자.

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

그럼, 오늘도 역시 세준이는 0부터 9까지 모든 한 자리수가 자리수로 등장하면서, 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N이면서 0에서 9가 모두 등장하는 계단 수가 총 몇 개 있는 지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 

10

예제 출력 

1

1. 접근

계단수는 인접한 자리수의 차이가 모두 1인 수를 일컫는다. 987654321 같은 수가 대표적이다.

쉬운 계단수 문제 ( http://js1jj2sk3.tistory.com/38 ) 에서 자리수가 n으로 주어지면

그런 계단수가 몇개 있는지는 O(10*N)에 구할 수 있었다.

그러면 그중에서 문제처럼 0 부터 9 까지 전부 있는 계단수는 몇개 인지 어떻게 알 수 있을까?

2. 풀이

쉬운 계단수 문제 처럼 생각해보자.

길이가 n인 계단수로 길이가 n+1인 계단수를 만들 수 있었다. n인 수의 마지막 수와 차이가 1나는 수를 뒤에 붙여주면 됐었다.

하지만 이제는 지금까지 무슨 수를 써왔는지까지 반영해야 한다.

그러면 모든 경우의 수를 무지막지하게 따지기로 하자. 계산은 컴퓨터가 해줄테니 걱정없다.

쉬운 계단수 문제처럼 DP[n][x] 배열을 만들자. n은 자리수, x는 맨 마지막 자리의 숫자이다.

하지만 이번 문제에선 지금까지 쓴 자리수를 기억해야하니,

DP[n][x][a0][a1]...[a9] 를 만들 수도 있다. a0 ~ a9 는 각기 0 ~ 9 를 썼는지에 대한 정보를 담을 것이다.

하지만 이제 계산을 어떻게 시켜야할지 코드가 매애우 어려워진다. (본인은 그럼)

그래서 차라리 DP[n][x][2 ^ 10] 짜리 배열로 만든다.

그러면

DP[10][0][1111111111(이진수)] = 10자리면서 1의 자리수는 0이며, 0 ~ 9 까지 모두 사용한 계단 수의 갯수

같은 정보를 담을 수 있다.

1111111111(2진수)가 나타내는 것은 0 ~ 9 까지 사용한 수의 상태를 0 / 1비트로 나타내고 있는 것이다.

(뒤에서 부터 0,1,2, ...)

계산을 컴퓨터에게 어떻게 맡길까?

1자리인 계단수는 9개가 있다. DP[1][X][2 ^ X] = 1 로 기저사례가 된다.

2자리인 계단수부터 점화식으로 구할 수 있다.

DP[N][X][상태비트 OR 2 ^ X] = DP[N - 1][X - 1][상태비트] + DP[N - 1][X + 1][상태비트]

상태비트를 OR 연산으로 사용한 숫자에 해당하는 비트를 세우고 넘겨주는 것이다.

따라서 가장 큰 포문 : 자리수에 해당 / 그 안에 포문 : 마지막으로 쓴 수 0 ~ 9 에 해당 / 그 안에 마지막 포문 : 가능한 모든 상태비트

로 삼중포문으로 계산할 수 있다. -> O(N * 10 * ( 2 ^ 10 )).

코드로 확인해보자.

3. 코드

#include <stdio.h>
using namespace std;
 
#define mod 1000000000
 
int n, i, j, k, ans;
int dp[101][10][1 << 10];
 
int main() {
    scanf("%d", &n);
 
    int full = (1 << 10) - 1;
 
    for (j = 1; j <= 9; ++j)
        dp[1][j][1 << j] = 1;
 
    for (i = 2; i <= n; ++i) {
        for (j = 0; j <= 9; ++j) {
            for (k = 0; k <= full; ++k) {
                if (j == 0)
                    dp[i][0][k | (1 << 0)] = (dp[i][0][k | (1 << 0)] + dp[i - 1][1][k]) % mod;
                else if (j == 9)
                    dp[i][9][k | (1 << 9)] = (dp[i][9][k | (1 << 9)] + dp[i - 1][8][k]) % mod;
                else {
                    dp[i][j][k | (1 << j)] = (dp[i][j][k | (1 << j)] + dp[i - 1][j - 1][k]) % mod;
                    dp[i][j][k | (1 << j)] = (dp[i][j][k | (1 << j)] + dp[i - 1][j + 1][k]) % mod;
                }
            }
        }
    }
 
    for (j = 0; j <= 9; ++j)
        ans = (ans + dp[n][j][full]) % mod;
 
    printf("%d", ans);
 
    return 0;
}