[Algorithm] 백준 10844 - 쉬운 계단 수 (JAVA)

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

10844번: 쉬운 계단 수

---

 

알고리즘 

N이 100까지 이므로, Long타입을 통한 dp 배열을 생성해야 한다. 특히 인접한 모든 자릿수의 차이가 1이라는 것에서 0과 9일 때 예외처리를 해주어야 한다. 또한, N=1일 때 모든 수가 계단 수 이므로 dp[1][0~9]를 1로 초기화 해주어야 한다. 

i번째 자릿수가 0일 때 다음 자릿수의 값 : 1 , i번째 자릿수가 9일 때 다음 자릿수의 값 : 8 , 나머지  i+1, i-1 이 된다. 

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static Long[][] dp; // 탐색 여부 (null) 판단을 위해 객체형으로 생성
    static int n;
    final static long DIV = 1_000_000_000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dp = new Long[n+1][10];

        // n이 1자릿수 일 때는 모든 수가 계단 수 이므로 1로 초기화 해준다.
        for (int i=0; i<=9; i++) dp[1][i] = 1L;
        long answer = 0;
        // 마지막 자릿수의 경우의 수를 모두 더해준다.
        for (int i=1; i<=9; i++) {
            answer += chk(n, i);
        }
        System.out.println(answer % DIV);
    }

    static long chk(int n, int pos) {
        if (n == 1) return dp[n][pos];
        // 탐색하지 않았을 경우
        if (dp[n][pos] == null) {
            if (pos == 0) {
                dp[n][pos] = chk(n-1,1);
            }
            else if (pos == 9) {
                dp[n][pos] = chk(n-1, 8);
            }
            else {
                dp[n][pos] = chk(n-1,pos-1) + chk(n-1, pos+1);
            }
        }
        return dp[n][pos] % DIV;
    }
}