[백준 10844] 쉬운 계단 수 (Java) - 다이나믹 프로그래밍

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

쉬운 계단 수

문제

45656이란 수를 보자.

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

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

입력

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

출력

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

예제 입력 1 복사

1

예제 출력 1 복사

9

예제 입력 2 복사

2

예제 출력 2 복사

17

 

---

풀이

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

public class Main {
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long[][] D = new long[N+1][10]; // 길이 N 계단 수 중, n으로 끝나는 계단 수 개수
        long mod = 1000000000;

        // 이미 아는 수 입력
        D[1][0] = 0; // 길이 0이고, 0으로 끝나는 계단수는 없다.

        // 길이 1이고, i로 끝나는 계단수는 1개씩
        for(int i=1; i<=9; i++){
            D[1][i] = 1;
        }

        for(int i=2; i<=N; i++){
            D[i][0] = D[i-1][1] % mod;
            D[i][9] = D[i-1][8] % mod;
            for(int j=1; j<=8; j++){
                D[i][j] = (D[i-1][j-1] + D[i-1][j+1]) % mod;
            }
        }

        long sum = 0;
        for(int i=0; i<=9; i++){
            sum = (sum + D[N][i]) % mod ;
        }

        System.out.println(sum);
    }
}

• 다이나믹프로그래밍을 활용한 문제
• 계단수는 인접한 수가 서로 1차이 씩날 때 계단수라고 부른다.
• 2차원 배열을 선언해서, 길이가 N인 계단 수 중, 마지막 수가 i인 계단수의 개수(D[N][i])를 저장한다.
•  거의 모든 문제가 풀렸다고 가정해보기
  • 길이가 n인 계단수 중에서 마지막 숫자가 i인 계단수(D[N][i])의 개수를 알고싶다고 가정해보자.
  • 계단수는 1차이씩 나기 때문에 D[N][i]는 D[N-1][i-1]과 D[N-1][i+1]로 부터 왔을 것이다. 
• 일반 점화식
  • 즉, D[N][i] = D[N-1][i-1] + D[N-1][i+1]이다.
  • 단, i가 0,9일때는 i-1, i+1이 배열의 범위를 넘어서기 때문에 유의한다.
  • D[N][0] = D[N-1][1]
  • D[N][0] = D[N-1][8]이다.