쉬운 계단 수

45656

이 수는 모든 자리수의 차이가 1이 난다. 이런 수가 계단수.

첫째 줄에 N이 주어지고 N은 1<=N<=100

10^100까지 커질 수 있다. 브루트포스로 할 수 있는 크기가 아니다.

이걸 알고서도 점화식 떠오르는게 없어서 브루트포스처럼 bottom-up으로 푸는 점화식을 생각했다.

D[N] : N의 계단 수인지 아닌지
S[N] : N의 자리수
D[N] = D[S[0] + S[1]] || D[S[1] + S[2]] || D[S[n-2] + S[n-1]]
// D[N]이 true면 cnt++;

n이 10^100인 경우, 최악의 경우 10^99 * 10^100 인데, 시간초과 날 수 밖에 없다.

걍 풀이를 보자.

D[N] => 길이가 N인 계단수.

위 점화식은 마지막 수에 대한 정보를 담고 있지 않다. (갑자기?)

점화식을 정의하기 위해 자리수별로 점화식을 세우려는 의도같다.

D[N][L] : 마지막 수가 L이고 길이가 L인 계단 수

?  ?     L+1 | L-1    L
[1][2]...   [N-1]    [N]

L앞에 올 수 있는 수는 L-1, L+1인데, 이 때 계단 수는 D[N-1][L+1], D[N-1][L-1] 즉, D[N][L] = D[N-1][L-1] + D[N-1][L+1]

풀어보자.

long long dp[101][10];

    long long n;
    cin>>n;

    long long size = n;

    long long mod = 1000000000;

//    fill_n(dp, size, 0); // 0: 미정, 1: true, -1: false
    for(int i = 1; i<=9; i++) {
        dp[1][i] = 1;
    }

    for(int i = 2; i<=size; i++) {
        for(int j = 0; j<=9; j++) {
            dp[i][j] = 0;
            if(j-1>=0) {
                dp[i][j] += dp[i-1][j-1];
            }
            if(j+1<=9) {
                dp[i][j] += dp[i-1][j+1];
            }
            dp[i][j] %= mod;
        }
    }

    long long result = 0;

    for(int i = 0; i<=9; i++) {
        result += dp[size][i];
    }

    cout<<result % mod<<endl;

Summary

자리 수 문제는 자리수 별로 점화식을 세워서 풀 수 있다는 생각을 해야겠다.