[백준 10844번] 쉬운 계단 수 - DP

 

백준 10844번 동적 계획법(Dynamic Programming)으로 풀 수 있는 문제이다.

10844번: 쉬운 계단 수

 

문제는,

45656이란 수가 있다.
이 수를 잘보면 각 자리수마다 1씩 차이나는 것을 알 수 있다. 이런 수를 계단 수라고 한다.
그렇다면 길이가 N개인 계단 수는 몇 개가 나올 수 있는지 구하는 것이 문제이다.

단, 마지막 정답에 1,000,000,000으로 나눈 나머지를 출력한다.

이 문제를 풀면서 주의해야할 점은 0으로 시작하는 숫자는 없다는 것이다.

즉, 0~9까지의 각 자리수가 있지만 첫 자리에는 0이 절대 올 수 없다는 것이다.

 

그렇다면 DP로 풀기 위해 먼저 첫 자리 수 먼저 생각해보자.

1~9까지의 숫자가 올 수 있다.

 

그럼 두 번째 자리 숫자를 생각해보자.

 

1인 경우에는 1, 0

2인 경우에는 1, 3

3인 경우에는 2, 4

...

9인 경우에는 8

 

이 정도까지오면 혹시 감이 오시나요⁉️

대략 (1, 2를 생각했을 때) 이런 그림의 모식도가 생겨납니다.

 

보시면 0이 되는 경우와 9가 되는 경우가 각각 이전 계단이 1인 경우, 8인 경우에만 만들 수 있다는 것을 알 수 있죠?

9의 경우에는 그림이 짤리는데 전 계단이 8인 경우에만 가능하겠죠.

 

그렇다면 다음과 같은 점화식을 세울 수 있습니다.

// N번째 수가 0인 경우
DP[N][0] = DP[N-1][1];

// N번째 수가 9인 경우
DP[N][9] = DP[N-1][8];

// 그 외 1~8인 경우
DP[N][i] = DP[N-1][i-1] + DP[N-1][i+1];

 

이제 점화식을 이용해서 첫 번째 수의 초기 조건만 만들고 진행시키면 되겠죠.

 

전체 코드를 보면

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

public class BAEKJOON10844 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[][] DP = new int[N+1][10];


        for (int i = 1; i <= 9; i++) {
            DP[1][i] = 1;
        }

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


        long answer = 0;
        for (int i = 0; i <= 9; i++)
            answer += DP[N][i];

        System.out.println(answer%1000000000);
    }
}