쉬운 계단 수

문제

45656이란 수를 보자.

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

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

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

입력

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

출력

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

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

풀이

45656처럼 이웃한 두 자릿수의 차이가 모두 1이면 계단 수다. 길이 2에서는 10과 12가 둘 다 유효하지만 11은 아니다. 앞자리에 0을 둘 수 없다는 제약과, 끝자리가 0 또는 9일 때 다음 선택지가 하나뿐이라는 점이 핵심이다.

길이만 상태로 두면 마지막 자릿수가 0인지 9인지에 따라 다음에 붙일 수 있는 숫자가 달라진다. 그래서 dp[i][d]를 길이 i이고 마지막 숫자가 d인 계단 수의 개수로 둔다. 첫 자리에 0은 올 수 없으므로 dp[1][1..9]=1, dp[1][0]=0이다.

마지막 숫자 d 바로 앞에는 d-1 또는 d+1만 올 수 있다. 즉 dp[i][d] = dp[i-1][d-1] + dp[i-1][d+1]인데, 범위 밖 숫자는 제외한다. 마지막이 0이면 앞은 1뿐이고, 마지막이 9이면 앞은 8뿐이다. 예를 들어 길이 2에서 마지막이 1인 수는 21 하나다. 01은 첫 자리 0 때문에 없다. 길이 2 전체를 합하면 17이 된다.

마지막 자릿수로 나누면 서로 다른 수가 같은 칸에 중복으로 들어가지 않는다. 길이 1에서 1부터 9까지 각 칸이 1인 상태로 시작해 길이 2를 계산하면 다음과 같다.

마지막 자리 `d`	0	1	2	3	4	5	6	7	8	9
`dp[2][d]`	1	1	2	2	2	2	2	2	2	1

끝자리가 2인 두 수는 12와 32다. 끝자리가 0인 수는 10 하나뿐이다. 이 행의 합은 1+1+7×2+1=17로 예제 출력과 일치한다. 길이 3의 마지막 자리 1은 길이 2의 마지막 자리 0과 2에서 오므로 dp[3][1]=1+2=3이다. 이런 식으로 짧은 수에 마지막 한 자리만 덧붙이는 것이 점화식의 계산 순서다.

코드는 각 상태마다 모듈러를 적용한 뒤 마지막 행의 10개 칸을 합친다. N=100일 때 경우의 수가 커지므로 마지막에만 나머지를 구하며 정수 오버플로를 감수하면 안 된다. 시간 O(10N), 표 전체를 보관하는 공간 O(10N)이다. N=1에서는 초기화한 1~9의 합인 9가 바로 답이다.

각 칸은 이전 행의 최대 두 칸만 더하므로 코드의 안쪽 반복문이 d=0..9를 순회하면서 범위 안인 이웃만 선택한다. 중간에 mod를 적용해도 (a+b) mod m = ((a mod m)+(b mod m)) mod m이라 최종 나머지는 같다. 마지막 행의 열 10개 합은 최대 약 100억이 될 수 있어 long solv가 필요하다. 전체 표 대신 길이 i-1과 i의 10칸 배열 두 개를 교대로 사용하면 공간 O(10)으로 줄일 수도 있다.

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        out.write("" + easyStair(n));
        out.write("\n");
        out.flush();
        out.close();
        in.close();
    }

    public static long easyStair(int n) {
        long mod = 1000000000L;
        long[][] dp = new long[n + 1][10];
        for (int i = 1; i <= 9; i++) {
            dp[1][i] = 1;
        }
        for (int i = 2; i <= n; 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 solv = 0;
        for (int i = 0; i <=9; i++) {
            solv += dp[n][i];
        }
        return solv %= mod;
    }
}