[동적계획법 (D.P.)] 백준 10844: 쉬운 계단 수, Java

1. 접근

1자리 수일 경우부터 생각해보기로 했습니다.

 

n = 1 일 때 1, 2, 3, 4, 5, 6, 7, 8, 9의 계단 수가 존재했습니다.

n = 2 일 때 10, 12, 21, 23, ... , 98의 계단 수가 존재했습니다.

n = 3 일 때 101, 121, 123, 210, 212, 232, 234, ... , 987, 989의 계단 수가 존재했습니다.

 

즉, 각 계단 수의 끝 자리의 수인 0 ~ 9에 의해 n + 1 자리 수의 계단 수가 추가되었습니다.

그래서 각 끝 자리의 수가 몇 번 나오는가를 저장할 배열이 필요했기에 2차원 배열을 사용하기로 하였습니다.

 

2. 해결

1부터 n의 자리 수의 끝 자리 수가 몇 번 나왔는지 그 개수를 중첩하여 저장하도록 합니다.

n의 자리 수까지 다 구하고 0 ~ 9 가 나온 개수의 합계를 구하면 총 n의 자리 수의 계단 수가 구할 수 있었습니다.

 

3. 코드

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());
        int[][] dp = new int[n + 1][10]; // n의 자리수 까지, 0 ~ 9 까지
        final int MOD = 1000000000;
        int ans = 0;

        for (int i = 1; i < 10; i++) {
            // 1의 자리일 때 1 ~ 9 까지만 존재하므로 각 숫자별로 1로 초기화
            dp[1][i] = 1;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < 10; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i - 1][1] % MOD; // 0은 1로 부터로만 나오게 됨
                } else if (j == 9) {
                    dp[i][j] = dp[i - 1][8] % MOD; // 9는 8로 부터로만 나오게 됨
                } else {
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
                }
            }
        }

        for (int i = 0; i < 10; i++) {
            ans = (ans + dp[n][i]) % MOD;
        }

        System.out.println(ans);
    }
}