백준 10844 쉬운 계단 수 Java: 자리수 DP와 모듈러 연산

백준 10844번 ‘쉬운 계단 수’는 인접한 두 자리의 차이가 1인 N자리 수의 개수를 구한다. 마지막 숫자가 무엇인지에 따라 다음에 붙을 수 있는 숫자가 정해지므로 길이와 마지막 자리를 DP 상태로 둔다.

• 백준 10844번 쉬운 계단 수

마지막 자리로 상태를 정의한다

dp[digit]를 현재 길이에서 digit으로 끝나는 계단 수의 개수라고 하자.

• 마지막이 0이면 이전 자리는 1만 가능
• 마지막이 9이면 이전 자리는 8만 가능
• 마지막이 1부터 8이면 이전 자리는 digit-1 또는 digit+1

next[0] = dp[1]
next[9] = dp[8]
next[d] = dp[d - 1] + dp[d + 1], 1 ≤ d ≤ 8

한 자리 수에서는 1부터 9까지가 각각 하나의 계단 수다. 0으로 시작하는 수는 N자리 수가 아니므로 dp[0] = 0으로 시작한다.

Java 코드

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

public class Main {
    private static final long MOD = 1_000_000_000L;

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        int length = Integer.parseInt(reader.readLine());

        long[] dp = new long[10];
        for (int digit = 1; digit <= 9; digit++) {
            dp[digit] = 1;
        }

        for (int currentLength = 2; currentLength <= length; currentLength++) {
            long[] next = new long[10];
            next[0] = dp[1];
            next[9] = dp[8];

            for (int digit = 1; digit <= 8; digit++) {
                next[digit] = (dp[digit - 1] + dp[digit + 1]) % MOD;
            }

            dp = next;
        }

        long answer = 0;
        for (long count : dp) {
            answer = (answer + count) % MOD;
        }

        System.out.println(answer);
    }
}

모듈러는 GCD가 아니다

원문에는 결과를 10억으로 나누기 위해 유클리드 호제법을 사용한다고 적었지만, 실제 code는 덧셈 결과에 % MOD를 적용했다. 유클리드 알고리즘은 최대공약수를 구하는 방법이고 이 문제의 modulo reduction과는 관계가 없다.

덧셈에서는 다음 성질로 중간 결과를 줄일 수 있다.

(a + b) mod M
= ((a mod M) + (b mod M)) mod M

long을 사용하고 각 transition과 최종 합에서 modulo를 적용한다. 현재 길이와 다음 길이 두 배열만 있으면 되므로 공간은 O(10), 시간은 O(10N), 즉 O(N)이다.

padding을 떠올려 푼 기록

원문에는 0과 9의 예외를 매번 branch로 처리하지 않으려고 양옆에 빈 index를 둔 padding 배열을 사용했다고 적혀 있다. 약 50분이 걸렸고, 비슷한 등급의 앞선 DP보다 상대적으로 쉽게 느꼈다고 남겼다.

padding도 유효하지만 digit과 array index가 한 칸씩 어긋나 읽을 때 변환이 필요하다. 이번 code는 0과 9만 명시하고 실제 digit을 그대로 index로 사용했다. 중요한 것은 표현 방식보다 “leading zero 금지”를 base case에서 처리하고 이후에는 마지막 자리만 상태로 남기는 것이다.

색상 선택을 마지막 상태로 두는 DP는 백준 1149 RGB거리에서 비교할 수 있다.

검증 범위

Java source를 수동 검토하고 N = 1, 작은 길이의 모든 숫자 직접 열거, 최대 길이와 random length를 exhaustive generator·2D DP oracle과 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.