[062] 10844. 쉬운 계단 수

✨ 알고리즘 분류 : 다이나믹 프로그래밍

 

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

10844번: 쉬운 계단 수

 

 

 

---

 

 

🪡 문제에서 요구하는 조건 정리

 

- 계단은 인접한 자리의 수의 차이가 모두 1인 수이다.

- 0으로 시작하는 수는 계단 수가 아니다.

- 길이가 n인 수 중 계단 수는 모두 몇 개인지 구하라

 

 

 

🧶 풀이과정 

 

계단 수는 인접한 모든 자리의 수 차이가 1인 수라고 하면, 이걸 어떻게 구할 수 있을까? 이럴 때는 우선 그려보자.

 

 

여기까지만 봐도 알겠지만

1. 마지막 자리가 0일 경우 이전 자릿수는 무조건 1이어야 한다. (10, 210, 3210 등등등등)

2. 마지막 자리가 9일 경우 이전 자릿수는 무조건 8이어야 한다. (89, 789, 989 등등등등)

3. 그게 아니라면 이전 자릿수 +1과 -1이 마지막 자릿수이다.

 

이것을 생각해서 코드를 작성하도록 하면 된다.

 

 

 

🏹 제출코드

 

package data_structure_part_01;

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

public class Q10844 {

    static Long[][] dp;
    static long mod = 1000000000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        dp = new Long[n+1][10];

        for(int i = 0; i < 10; i++){
            dp[1][i] = 1L;
        }

        long sum = 0;
        for(int i = 1; i <= 9; i++){
            sum += cal(n, i);
        }

        System.out.println(sum % mod);

        br.close();


    }


    static long cal(int num, int val){


        if(num == 1){
            return dp[num][val];

        }

        if(dp[num][val] == null ) {


            if (val == 0) {
                dp[num][val] = cal(num - 1, 1);
            } else if (val == 9) {
                dp[num][val] = cal(num - 1, 8);
            } else {
                dp[num][val] = cal(num - 1, val - 1) + cal(num - 1, val + 1);
            }

        }



        return dp[num][val] % mod;
    }
}