[백준] 10844번 : 쉬운 계단 수 (JAVA)

인간몽쉘김통통·2023년 11월 23일

다이나믹 프로그래밍 백준 알고리즘

백준

목록 보기

23/92

문제

이해

계단수는 인접 자리의 수가 1씩 차이나는 수이다.

자리수를 N이라고 할 때

N=1이면, (1, 2, 3, 4, 5, 6, 7, 8, 9)
N=2이면, (10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98)
...

이 계단수가 된다.

접근

계단수의 특징을 보자. 계단수는 인접 자리수의 차이가 1인 수이다. 그렇다면 계단수를 어떻게 만들면 좋을까?

계단수는 이전 자리의 영향을 받는다. 그렇다면 N자리의 계단 수는 N-1자리 계단수의 영향을 받을 수 밖에 없다.

N=2인 경우를 보자.
(10, 12)은 1에서 파생된다.
(21, 23)은 2에서 파생된다.

이처럼 N과 N-1의 계단수는 각 끝자리 수가 몇개 있는지에 따라서 결정된다.

표는 각 층 별로 끝 자리수의 개수를 기록한 것이다. (편의상 N을 층이라고 하자.)

i층의 정보를 구하고 싶다면 i-1층의 정보를 보면 된다.
i층의 0 : i-1층의 1
i층의 1 : i-1층의 0 + i-1층의 2
i층의 2 : i-1층의 1 + i-1층의 3
.
.
.
i층의 9 : i-1층의 8

즉, 위와 같은 점화식을 통해 다이나믹 프로그래밍을 적용하면 N층의 계단 수 정보를 구할 수 있다.

물론, N은 최대 100이기 때문에 계산하는 과정에서 1000000000이 넘어갈 수 있기 때문에 나머지 연산을 수시로 해주어야 한다.
(직접 해보니 N이 35쯤에서 int형 범위를 벗어난다.)

코드

package java_baekjoon;

import java.io.*;

public class prob10844 {
    static final int MOD = 1000000000;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] prev_arr = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1};
        int ans = 0;

        
        for(int i=2; i<=N;i++){
            int[] arr = new int[10];
            for(int j=0;j<=9;j++){
                if(j == 0){
                    arr[j] = prev_arr[1]; 
                } else if(j == 9){
                    arr[j] = prev_arr[8];
                } else{
                    arr[j] = prev_arr[j-1] + prev_arr[j + 1];
                }
                arr[j] %= MOD;
            }
            prev_arr = arr;
        }

        for(int i=0;i<=9;i++){
            ans += prev_arr[i];
            ans %= MOD;
        }

        System.out.println(ans);
    }
}