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

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

10844번: 쉬운 계단 수

풀이

사용한 알고리즘 : 다이나믹 프로그래밍(DP)

 

풀이전략

 

인접한 계단 사이의 차이는 1이라고 했으므로

다음 특정 값의 계단에서 가질 수 있는 경우의 수는

이전 계단이 현재의 계단 값보다 1 작을 경우의 수 더하기 계단 값이 1 클 경우의 수이다.

 

단, 0과 같은 경우는 수에 음수가 들어갈 수 없으므로

이전 계단값이 현재 계단 값보다 1 더 클 경우의 수만을 가질 수 있다.

 

9 또한 이전 계단 값으로 10을 가질 수 없으므로

이전 계단 값이 8인 경우의 수만을 가진다.

 

이를 수식으로 나타내면 아래와 같다.

 

마지막으로 d[n][0]~ d[n][9] 까지의 모든 수의 합을 구하면 우리가 구하는 정답이 도출된다.

 

제출코드

import java.io.*;

public class Main{
    static int N;
    static int d[][];
    static int resultCount=0;
    static int mod=1000000000;
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        d = new int[N+1][10];

        d[1][0]=0;
        for(int i=1;i<=9;++i){
            d[1][i]=1;
        }

        for(int i=2;i<=N;++i){
            d[i][0]=d[i-1][1];
            for(int j=1;j<9;++j){
                d[i][j]=(d[i-1][j-1]+d[i-1][j+1])%mod;
            }
            d[i][9]=d[i-1][8];
        }

        int sum=0;
        for(int i=0;i<=9;++i){
            sum+=d[N][i];
            sum%=mod;
        }

        bw.write(sum+"\n");
        bw.flush();
        bw.close();
    }
}