BOJ 10844 - 쉬운 계단 수

문제

BOJ 10844 - 쉬운 계단 수

인접한 자리의 숫자 차이가 항상 1인 N자리 수를 계단 수라고 한다. 예를 들어 45656이 계단 수다. N이 주어질 때 계단 수의 개수를 1,000,000,000으로 나눈 나머지를 구하는 문제다. 단, 0으로 시작하는 수는 계단 수가 아니다.

입력

• 첫째 줄: N (1 ≤ N ≤ 100)

출력

N자리 계단 수의 개수를 1,000,000,000으로 나눈 나머지를 출력한다.

예제

풀이

2차원 DP dp[자릿수][마지막 숫자]를 정의하고 Top-Down 메모이제이션으로 계단 수의 개수를 센다. 마지막 자리가 0이면 이전 자리는 1만 가능하고, 9이면 이전 자리는 8만 가능하며, 그 외에는 이전 자리에서 ±1이 가능하다.

1. dp[1][v] = 1로 초기화한다 (1자리 계단 수는 1~9 각각 1개).
2. recur(n, v) 함수는 n자리이고 마지막 숫자가 v인 계단 수의 개수를 반환한다.
3. 점화식:
   • v == 0: dp[n][0] = recur(n-1, 1) (이전 자리는 1만 가능)
   • v == 9: dp[n][9] = recur(n-1, 8) (이전 자리는 8만 가능)
   • 그 외: dp[n][v] = recur(n-1, v-1) + recur(n-1, v+1)
4. 매 계산마다 % 1,000,000,000으로 나머지를 관리한다.
5. N자리 계단 수는 sum(recur(N, 1) ~ recur(N, 9))이다 (0으로 시작하는 수 제외).

핵심 아이디어: 현재 자릿수의 마지막 숫자가 결정되면, 다음 자릿수에서 선택 가능한 숫자는 ±1로 고정된다. 경계 조건(0과 9)을 별도 처리하는 점화식으로 계단 수의 개수를 효율적으로 계산한다.

코드

package com.ssafy.an.day099;
 
import java.util.Scanner;
 
public class Day71BOJ10844쉬운계단오르기DP { // 10844 쉬운? 계단 오르기
	static final int SIBUK = 1_000_000_000;
	static int N;
	static Long[][] dp;
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		dp = new Long[N + 1][10];
		System.out.println(solve());
		sc.close();
	}
 
	private static long solve() {
		for (int i = 0; i < 10; i++)	dp[1][i] = 1L;
		long res = 0;
		for (int i = 1; i < 10; i++)	res += recur(N, i);
		return res % SIBUK;
	}
	// 점화식 찾는 게 중요하다. 1, 9의 예외와 나머지 분리.
	private static long recur(int n, int v) {
		if (n == 1)				return dp[n][v];
		if (dp[n][v] != null)	return dp[n][v] % SIBUK;
		if (v == 0)				dp[n][v] = recur(n - 1, 1);
		else if (v == 9)		dp[n][v] = recur(n - 1, 8);
		else					dp[n][v] = recur(n - 1, v - 1) + recur(n - 1, v + 1);
		return dp[n][v] % SIBUK;
	}
}

복잡도

• 시간: O(N * 10) = O(N) — 자릿수 N과 숫자 0~9에 대해 각 한 번씩 계산
• 공간: O(N * 10) = O(N) — dp 배열 (N+1) x 10 크기