[백준] 10844: 쉬운 계단 수 - Java (DP)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

 

  접근 방식

 

나는 먼저 N=1, 2, 3, 4일 때를 가정해서 손으로 직접 작성해 보았다.

 

[숫자] 는 해당 숫자로 끝나는 수를 말한다.

 

 

각 n 마다 0~3만 해보아도 알 수 있다.

 

 

  핵심

n = 3일 때를 가정해 보자. 0과 9를 제외하면 모두 n - 1 에서 그 전 숫자와 그 다음 숫자의 합이라는 것을 알 수 있다.

말로 하면 어려운데 n = 3이고 2로 끝나는 수를 보자. 212, 232, 432 이렇게 3개 이다. 

이제 다시 n - 1(= 2)이고, 1로 끝나는 수와 3으로 끝나는 수를 보자. 21, 23, 43 이렇게 3개 이다. 다시 돌아가 n = 3, 2로 끝나는 수를 보면 지금 이 숫자들에 2를 붙인 수들이다. 

 

 

그럼이제 점화식을 세울 수 있게된다. 

1~8로 끝나는 숫자들은 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1]dp[j + 1];

 

 

이제 예외처리를 해주어야 한다. 사실 예외처리는 먼저 해주는 편이지만, 핵심을 이야기 하기 위해서 지금으로 미루었다.

0과 9로 끝나는 숫자들은 이전에 양쪽 숫자에서 더하는 1~8로 끝나는 숫자들과는 다르게 한 쪽에서만 가능하다.

즉, 0으로 끝나는 숫자는 이전 숫자가 무조건 1이어야 하고, 9로 끝나는 숫자는 이전 숫자가 무조건 8이어야 한다.

 

그렇다면

0은 dp[i][0] = dp[i - 1][1];

9는 dp[i][9] = dp[i - 1][8];

 

이렇게 예외처리를 해줄 수 있을 것이다.

 

 

 

  풀이

 

package src.dp;

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

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

        // dp[자리수][으로 끝나는 수] = 개수
        int[][] dp = new int[n + 1][10];

        // 한 자리 수에 대한 로직
        for(int i = 1; i < 10; i++){
            dp[1][i] = 1;
        }

        // 마지막 숫자가 0인 경우 이전 숫자가 무조건 1이어야 함.
        // 마지막 숫자가 9인 경우 이전 숫자가 무조건 8이어야함.

        // 두 자리 수 이상에 대한 로직
        for(int i = 2; i <= n; i++){
            for(int j = 0; j < 10; j++){
                if(j == 0) {
                    dp[i][j] = dp[i - 1][1] % 1000000000;
                } else if(j == 9) {
                    dp[i][j] = dp[i - 1][8] % 1000000000;
                } else {
                    dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000;
                }
            }
        }

        // 큰 수의 el 들의 값들을 더하면 (2^31 - 1)을 넘어갈 수 있으므로 long 타입으로 선언
        long result = 0;
        for(int el : dp[n]){
            result += el;
        }

        System.out.println(result % 1000000000);

    }
}