[Java] 백준 BOJ / 10844번: 쉬운 계단 수

쉬운 계단 수

문제

---

문제 설명

N이 주어질 때, N자리 수 중 계단 수 라는 것을 구하는 문제이다.

여기서 계단 수란 인접한 모든 자리의 차이가 1인 수를 뜻한다.

사실 이 문제를 처음 보자마자 DP로 풀겠다고 떠올리기는 힘들었지만 요즘 동적계획법에 있는 문제들을 풀고 있어서 DP로 방향을 잡고 풀었다.

DP를 풀 때 일단 경우의 수를 다 해보면 어느정도 가닥이 잡히기 때문에 세자리수까지 해봤다.

dp	0	1	2	3	4	5	6	7	8	9
1	0	1	2	3	4	5	6	7	8	9
2	01	10, 12	21, 23	32, 34	43, 45	54, 56	65, 67	76, 78	87, 89	98
3	010, 012	101, 121, 123	210, 212, 232, 234	321, 323, 343, 345	432, 434, 454, 456	543, 545, 565, 567	654, 656, 676, 678	765, 767, 787, 789	876, 878, 898	987, 989

이 표를 보면 뭔가 느낌이 올것이다.

보면 같은 숫자들이 반복되고 있다. 예를 들어 dp[3][2]에 있는 숫자들을 보자 210, 212, 232, 234 이다.
dp[2][1]에는 10, 12가 있고 dp[2][3]에는 32,34가 있고 2부터 8까지 모두 그런식으로 진행됨을 알 수 있고
현재의 위치가 x, y라면 dp[x][y] = dp[x-1][y-1] + dp[x+1][y-1] 이라는 점화식을 따른다는걸 알 수 있다.

그렇다면 만약에 N번째 자리가 0이라고 하면 그 전에 올 수 있는 수는 1밖에 없고
N번째 자리가 9라고 하면 그 전에 올 수 있는 수는 8밖에 없다는 것을 알 수 있을 것이다.

이런식으로 해서 자릿수를 나타내는 변수 digit과 자리값을 나타내는 변수val을 통해 아래와 같이 코드를 작성하였다.

---

코드

import java.util.Scanner;

public class Main_10844 {
    static int n;
    static int MOD = 1000000000;
    static Long[][] dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

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

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

        long result = 0;

        for (int i = 1; i <= 9; i++) {
            result += stair(n, i);
        }

        System.out.println(result % MOD);
    }

    public static long stair(int digit, int val) {
        if (digit == 1) {
            return dp[digit][val];
        }

        if (dp[digit][val] == null) {
            if (val == 0) {
                dp[digit][val] = stair(digit - 1, 1);
            } else if (val == 9) {
                dp[digit][val] = stair(digit - 1, 8);
            } else {
                dp[digit][val] = stair(digit - 1, val - 1) + stair(digit - 1, val + 1);
            }
        }
        return dp[digit][val] % MOD;
    }
}