백준 10844 "쉬운 계단 수" (JAVA)

🔍 문제링크

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

---

📌 문제 요약

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

• • 계단 수는 인접한 자리의 숫자 차이가 항상 1이어야 한다.
  • 첫 번째 자리는 0이 될 수 없다.
  • 정답을 1,000,000,000으로 나눈 나머지를 출력

---

🛠 풀이 및 알고리즘

1. DP 배열 정의
   • `dp[i][j]`: 길이가 i이고 마지막 숫자가 j일 때 계단 수의 개수
   • `dp[1][0] = 0` (첫 자리가 0이면 안됨)
   • `dp[1][1] ~ dp[1][9] = 1` (한 자리 계단 수는 자기 자신)
2. 점화식

 

• `dp[i][0] `= `dp[i+1][1]` (0은 이전 자리가 1인 경우만 가능)
• `dp[i][9]` = `dp[i-1][8]` (9는 이전 자리가 8인 경우만 가능)
• `dp[i][j]` = `dp[i-1][j-1] + dp[i-1][j+1]` (나머지 숫자는 양옆에서 오는 경우)
• 모든 값은 1,000,000,000으로 나눈 나머지를 저장

1. 결과 계산
   • `dp[N][0] ~ dp[N][9]` 값을 더하여 정답 도출

---

💡 코드

public class Baekjoon_10844 {
    static final int MOD = 1_000_000_000;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n == 1) {
            System.out.println(9);
            return;
        }
        int ans = 0;
        int[][] dp = new int[n + 1][10]; // 길이가 n이고 마지막 숫자가 L일때 계단 총 수

        Arrays.fill(dp[1], 1);
        dp[1][0] = 0;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= 9; j++) {
                switch (j) {
                    case 0 -> dp[i][j] = dp[i - 1][j + 1] % MOD;
                    case 9 -> dp[i][j] = dp[i - 1][j - 1] % MOD;
                    default -> dp[i][j] = (dp[i - 1][j + 1] + dp[i - 1][j - 1]) % MOD;
                }
            }
        }
        for (int i = 0; i <= 9; i++) {
            ans = (ans + dp[n][i]) % 1_000_000_000;
        }
        System.out.println(ans);
    }
}

---

🏆 시간 복잡도 분석

• dp[i][j]를 채우는 과정은 O(N × 10) = 최종 시간 복잡도: O(N)
• N ≤ 100 이므로 최악의 경우 O(1000)