BOJ10844 쉬운 계단 수

https://www.acmicpc.net/problem/10844 (opens new window)

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

접근 방법

Bottom Down을 활용한 방법이다. 쉬운 계단 수를 나타낼 수 있는 이차 배열 dp 테이블을 선언한다. 이차 배열은 자릿수와 맨끝자리 수를 표현하기 위해 사용한다.

long[][] dp = new long[n + 1][10];

만약 십의 자리수가 2인 숫자 중 계단수는 21, 23이 존재한다. 이것이 의미하는 것은 앞자리가 2인 경우 일의 자리가 1인 이전 경우 + 3인 경우로 표현이 가능하다. 이것을 식으로 표현하면 아래와 같다.

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];

이제 추가적으로 고려해야 할 점은 끝자리가 0인 경우와 9인 경우 이다. 끝자리가 0인 계단수가 되기 위해서는 앞자리가 1이어야만 가능하다. 9일때는 8이여야만 가능하다. 이 부분은 아래와 같이 해결한다.

if (j == 0) {
    dp[i][0] = dp[i - 1][1] % DIV;
    continue;
}

if (j == 9) {
    dp[i][9] = dp[i - 1][8] % DIV;
    continue;
}

제출 코드

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ10844 {

    public static final long DIV = 1_000_000_000;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        long[][] dp = new long[n + 1][10];

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

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < 10; j++) {

                if (j == 0) {
                    dp[i][0] = dp[i - 1][1] % DIV;
                    continue;
                }

                if (j == 9) {
                    dp[i][9] = dp[i - 1][8] % DIV;
                    continue;
                }

                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % DIV;
            }
        }

        long sum = 0;
        for (int i = 0; i < 10; i++) {
            sum += dp[n][i];
        }

        System.out.println(sum % DIV);
    }
}

#algorithm #BOJ #다이나믹 프로그래밍