문제

BOJ 10844: 쉬운 계단 수 https://www.acmicpc.net/problem/10844

풀이

조건

• 인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다.
• 길이가 N인 계단 수가 총 몇 개 있는지 구한다.

풀이 순서

• N번째 자릿수의 자릿값이 0인 경우에는 다음 자릿수의 자릿값은 1밖에 올 수 없다.
  • 20 같은 경우는 될 수 없기 때문이다.
  • 10 만 가능하다.
• N번째 자릿수의 자릿값이 9인 경우에는 다음 자릿수의 자릿값은 8밖에 올 수 없다.
  • 10_9 같은 경우는 될 수 없기 때문이다.
  • 89 만 가능하다.

코드

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        
        // N 자릿수에 각각의 자릿값(0~9)를 의미
        long[][] dp = new long[N + 1][10];

        // 1자리는 모두 1 경우 밖에 없다
        for (int i = 1; i < 10; i++) {
            dp[1][i] = 1;
        }

        for (int i = 2; i <= N; i++) {
            for (int j = 0; j < 10; j++) {
                // 자릿값이 0이면 이전 자릿수는 1만 가능
                if (j == 0) {
                    dp[i][0] = dp[i - 1][1] % 1_000_000_000;
                } 
                // 자릿값이 9이면 이전 자릿수는 8만 가능
                else if (j == 9) {
                    dp[i][9] = dp[i - 1][8] % 1_000_000_000;
                } 
                // 다른 숫자들은 이전 자릿수의 자릿값 +1, -1 한 숫자 가능
                else {
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1_000_000_000;
                }
            }
        }

        long answer = 0;
        // 모든 자릿수에 저장된 경우의 수 더하기
        for (int i = 0; i < 10; i++) {
            answer += dp[N][i];
        }

        System.out.println(answer % 1_000_000_000);
    }

}

정리

• 2차원 배열로 DP를 구현하는 아이디어를 배울 수 있었다.