[백준] 10844번 쉬운 계단

📖 문제

45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

✍ 입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

📄 출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

✅ 코드

import java.io.BufferedReader;  
import java.io.InputStreamReader;  
  
public class Main {  
    static final int DIVIDE_VALUE = 1_000_000_000;  
  
    public static void main(String[] args) throws Exception{  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        int N = Integer.parseInt(br.readLine());  
        int[][] arr = new int[N+1][10];  

		// (1) 길이가 1인 계단 수 초기화 (0 제외)
        for(int i=1; i<10; i++) {  
            arr[1][i] = 1;  
        }  

		// (2) DP 점화식 적용 (Bottom-Up 방식)
        for (int i = 2; i <= N; i++) {  
            for (int j = 0; j < 10; j++) {  
                if (j > 0) arr[i][j] = (arr[i][j] + arr[i - 1][j - 1]) % DIVIDE_VALUE;  
                if (j < 9) arr[i][j] = (arr[i][j] + arr[i - 1][j + 1]) % DIVIDE_VALUE;  
            }  
        }  

		// (3) 길이가 N인 계단 수 개수 합산 후 MOD 연산
        int result = 0;  
        for (int i = 0; i < 10; i++) {  
            result = (result + arr[N][i]) % DIVIDE_VALUE;  
        }  
  
        System.out.println(result);  
    }  
}

🧩 코드풀이

해당 문제는 bottom-up 방식 DP 알고리즘을 이용해서 문제를 풀었습니다.

1️⃣ 길이가 1인 경우 초기화

• 한 자리 숫자는 1~9까지 총 9개 존재한다.
• 0으로 시작하는 계단 수는 없으므로 arr[1][0] = 0 이고, 나머지는 1로 설정한다.

2️⃣ 점화식 적용

• 길이가 i이고 마지막 숫자가 j인 계단 수는 전 단계(i-1)에서 j-1이거나 j+1이었던 계단 수의 개수를 더한 값이다.
• 이때, 수가 너무 커지는 것을 방지하기 위해 각 연산마다 1,000,000,000으로 나눈 나머지를 저장한다.

3️⃣ 결과값 계산

• dp[N][0] ~ dp[N][9]의 값을 모두 합친 후, 1,000,000,000으로 나눈 나머지를 출력한다.