[백준] 10844번 쉬운 계단 수 JAVA DP

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

10844번: 쉬운 계단 수

 

문제 요약

숫자 N이 주어질 때 쉬운 계단 수가 될 수 있는 경우의 수의 합을 구하라.

쉬운 계단 수는 각 자리 앞뒤 수 와의 차이가 1인 수

예를 들면 123456

 

풀이방법

DP 중에서도 Bottom-up으로 풀이

문제의 포인트는 마지막 숫자가 무엇인가

예를 들어 2가 input으로 주어졌을 때 

한자리 수 쉬운 계단수의 조합으로 두자리 수를 구하게 되는데

0에서 파생될 수 있는 경우의 수는 01 뿐인데 반해

1에서 파생될 수 있는 경우의 수는 10과 12가 된다.

이런 경우는 0과 9에만 해당되며 나머지숫자는 앞뒤 배열의 합으로 표현할 수 있다.

 

구현 하면서의 포인트는

숫자의 크기가 크기 때문에 long타입으로 선언할것.

그리고 1000000000으로 나눠주되 중간중간 계산할 때에도 계속 나눌 것.

 

JAVA 코드

 

import java.io.*;

public class Main {
    final static long SUB = 1000000000;
    public static void main(String args[]) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int input = Integer.parseInt(reader.readLine());
        long[][] arr = new long[input+1][10];
        //한자리 수는 0빼고 1-9까지 1로 초기화
        for(int i=1; i<10; i++){
            arr[1][i] = 1;
        }
        
		//0과 9는 1과 8배열 만 가져올 수 있다. 
        for(int i=2; i<input+1; i++){
            for(int j=0; j<10; j++){
                if(j == 0){
                    arr[i][j] = arr[i-1][1] % SUB;
                }else if(j == 9){
                    arr[i][j] = arr[i-1][8] % SUB;
                }else{
                    arr[i][j] = (arr[i-1][j-1] + arr[i-1][j+1]) % SUB;
                }
            }
        }
        long sum = 0;
        for(int i=0; i<10; i++){
            sum += arr[input][i];
        }
        System.out.println(sum % SUB);
        reader.close();
    }
}