[BOJ-10844] 쉬운 계단 수(JAVA)

백준 10844 쉬운 계단 수

 

 

10844번: 쉬운 계단 수

 

 

문제 설명

 

 - 인접함 모든 자리의 차이가 1인 수를 계단 수라고 한다.

 

 - 예를 들어, 45656이라는 수는 인접한 모든 자리의 차이가 1이기 때문에 계단 수이다.

 

 - N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하라.

 

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

 

 - 정답을 1,000,000,000 으로 나눈 나머지를 출력하라.

 

 

---

 

입력 값

 

 - 첫째 줄에 N이 주어진다.(ㄴ1 <= N <= 100 인 자연수)

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 계단 수 라는 것은 인접한 수와 차이가 1인 수를 의미한다.

 

 - 즉, 계단수인지 확인하는 방법은 인접한 수의 차이가 1인지 확인하면 된다.

 

 - 그렇다면, 현재 N자리인 계단수가 있을 때, N+1 자리인 계단수를 만드는 방법은

   N자리 계단수의 마지막 숫자에서 +1 / -1을 하면 된다.

 

 - 이 것을 수식으로 만들어보면 된다.

 

 - DP[i][j] = i자리인 계단수의 마지막 숫자는 j인 계단수의 개수라고 가정하자.

 

 - DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1]가 된다.

   (j-1<0인 경우 DP[i-1][j-1]은 생략하고, j+1 > 9 인 경우 DP[i-1][j+1]은 생략한다.)

 

 

---

 

 

소스 코드

 

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

// https://www.acmicpc.net/problem/10844
// 쉬운 계단 수
public class Main {

    private static int dp[][] = new int[101][11];

    private static int dNum = 1000000000;

    private static int N=0;

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(bf.readLine());

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

        findStairsNum(2);

        int sum=0;

        for(int i=0;i<10;i++){
            sum=(sum+dp[N][i])%dNum;
        }

        System.out.println(sum);

    }

    public static void findStairsNum(int num){
        if(num>N){
            return ;
        }
        for(int i=0;i<10;i++){
            if(i!=0){
                dp[num][i]=dp[num-1][i-1];
            }
            if(i!=9){
                dp[num][i]+=dp[num-1][i+1]%dNum;
            }
            dp[num][i]%=dNum;
        }
        findStairsNum(num+1);
    }

}