[Java] 백준 #10844 (DP)

📍 출처

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

📝 문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

⌨️ 입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

🖨 출력

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

⌨️ 예제 입력

2

🖨 예제 출력

17

📚 내가 제출한 코드

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

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

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

        final long MOD = 1000000000;
        int N = Integer.parseInt(br.readLine());

        long arr[][] = new long[N + 1][10];

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

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

        long sum = 0;

            for(int j = 0 ; j < 10 ; j++){
                sum += arr[N][j];
            }

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

✏️ 내가 제출한 코드에 대한 설명

• DP로 해결 가능한 문제로 bottom - up, top - down 둘다 해결가능
• 첫 번째 자리수의 모든 자리값은 1 이다.
• 자리값이 0 or 9 일 땐 1개로 밖에 나눠질 수 없으므로 이때만 예외로 해결해준다.