백준 10844번 - 쉬운 계단 수

문제

백준 10844번 - 쉬운 계단 수

아이디어

• 인접한 모든 자리의 차이가 1이기 때문에 특정 수 x(0~9) 이전, 이후에 올 수 있는 수는 제한되어 있으므로 DP로 값을 채워나갈 수 있다.
• dp[n][x] 를 길이가 n, 마지막이 x인 계단 수의 개수라고 가정한다.
• 길이가 1일 때는 1부터 9까지 하나씩 가능하므로 dp[1][1~9] = 1로 초기화가 가능하다.
• 길이가 2 이상부터는 값을 채워나가면 되는데, 마지막이 0이나 9로 끝나면 전에는 각각 1과 8만 있을 수 있기 때문에 dp[n][0] = dp[n-1][1], dp[n][9] = dp[n-1][8]이 된다.
• 그 외 1~8은 전에 -1, +1한 수가 올 수 있기 때문에 dp[n][x] = dp[n-1][x-1] + dp[n-1][x+1]이 된다.
• 최종적으로 dp[n][0~9]의 총합이 정답이다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N)

코드 구현

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

public class BJ_10844 {

    static final int MOD = 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());

        //길이가 N이고, 마지막이 i인 계단 수
        int[][] dp = new int[n + 1][10];

        //길이가 1
        for (int i = 1; i < 10; i++) {
            dp[1][i] = 1;
        }

        //길이가 2 ~ N
        for (int i = 2; i <= n; i++) {
            
            dp[i][0] = dp[i - 1][1];
            dp[i][9] = dp[i - 1][8];

            for (int j = 1; j < 9; j++) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
                dp[i][j] %= MOD;
            }
        }

        int sum = 0;

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

        System.out.println(sum);
    }
}