[동적 계획법] 백준 10844번 쉬운 계단 수(Java)

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

📚 문제

45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

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

예제 입력	예제 출력
1	9
2	17

 

📝 문제 해설

테이블 정의

이 문제의 경우 2차원 배열을 사용해야 한다.

• dp[N][j] : 길이가 N이고 j(0~9)로 시작하는 수들 중 계단 수의 개수

 

점화식 세우기

예를 들어 N=3일 때, dp[3][3]는 32X 혹은 34X 이므로 dp[3][3]= dp[2][2] + dp[2][4]

따라서, dp[i][j] =  dp[i-1][j-1] + dp[i-1][j+1]

하지만 j가 0일 때는 dp[N][0] = dp[N-1][1]만 가능하고

j가 9일 때는 dp[N][9] = dp[N-1][8]만 가능하다.

 

초기값 정의

길이가 1일 때의 계단 수 개수 정의

길이 시작하는 수		0	1	2	3	4	5	6	7	8	9
0		X	1	2	3	4	5	6	7	8	9
1		01	10, 12	21, 23	32, 34	43, 45	54, 56	65, 67	76, 78	87, 89	98
2		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

 

💻 코드

package dynamicProgramming;

import java.util.*;

public class BOJ10844 {
    static long mod = 1000000000;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.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 == 9) dp[i][9] = dp[i - 1][8] % mod;
                else if (j == 0) dp[i][0] = dp[i - 1][1] % mod;
                else dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
            }
        }

        long result = 0;

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

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