쉬운 계단 수

문제 정보

• 백준 실버 1
• DP
• 문제 링크

풀이

길이 N인 계단 수의 개수를 구하는 문제다.

dp[i][j]를 길이가 i이고, 마지막 자리가 j인 계단 수의 개수로 정의한다.

길이가 i이고 마지막 자리가 j인 계단 수를 만들려면, 직전 자리는 j - 1 또는 j + 1이어야 한다. 즉, 길이가 i - 1이고 마지막 자리가 j - 1인 계단 수 뒤에 j를 붙이거나, 마지막 자리가 j + 1인 계단 수 뒤에 j를 붙이면 된다.

따라서 일반적인 경우의 점화식은 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]이 된다.

다만 j = 0과 j = 9인 경우는 한쪽 방향으로만 인접한 수가 존재하므로 따로 처리해야 한다.

• j = 0인 경우: 0의 인접한 수는 1뿐이므로, 마지막 자리가 1인 계단 수 뒤에 0을 붙이는 경우만 존재한다. → dp[i - 1][j], j = 0
• j = 9인 경우: 9의 인접한 수는 8뿐이므로, 마지막 자리가 8인 계단 수 뒤에 9를 붙이는 경우만 존재한다. → dp[i - 1][8], j = 9

코드

import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        int MOD = 1_000_000_000;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        long[][] dp = new long[n + 1][10];
        
        for (int j = 1; j <= 9; j++)
            dp[1][j]= 1;
        
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= 9; j++) {
                if (j == 0)
                    dp[i][0] = dp[i - 1][1] % MOD;
                else if (j == 9)
                    dp[i][9] = dp[i - 1][8] % MOD;
                else
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
            }
        }
        
        long result = 0;
        for (int j = 0; j <= 9; j++)
            result = (result + dp[n][j]) % MOD;
        
        System.out.println(result);
    }
}