[백준] 10844 쉬운 계단 수 자바(Java)

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

10844번: 쉬운 계단 수

 

1의 자릿수일 때

1 ~ 9까지 가능 -> 9가지

 

2의 자릿수일 때

1의 자릿수 1 ~ 9, 2의 자릿수 1의 자릿수의 값이 1, 9가 아니면 1의 자릿값 + 1과 1의 자릿값 - 1 2가지가 가능하게 된다.

 

dp테이블

자릿수, 자릿값을 가지고 있어야 한다.

-> dp[자릿수][자릿값]

 

초기화

dp[1][1~9] = 1; -> 첫 번째 자릿수는 오른쪽 맨 끝의 자릿수이므로 경우의 수가 1개밖에 없다

 

점화식

 

탑다운 자바 코드

package main.iyk2h;

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

public class Main {

    static Long[][] dp;
    final static long divVal = 1_000_000_000;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        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 < 10; i++) {
            result += L(n, i);
        }
        System.out.println(result % divVal);
    }

    static Long L(int n, int i) {
        if (n == 1) {
            return dp[n][i];
        }

        if (dp[n][i] == null) {
            if (i == 0) {
                dp[n][i] = L(n - 1, 1);
            } else if (i == 9) {
                dp[n][i] = L(n - 1, 8);
            } else {
                dp[n][i] = (L(n - 1, i - 1) + L(n - 1, i + 1));
            }
        }
        return dp[n][i] % divVal;
    }
}