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

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

10844번: 쉬운 계단 수

 

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[][] dp = new int[n+1][10];

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

        for(int i=2; i<=n; i++){
            for(int j=0; j<10; j++){
                if(j==0){
                    dp[i][j] = dp[i-1][j+1] % 1000000000;
                }
                else if(j==9){
                    dp[i][j] = dp[i-1][j-1] % 1000000000;
                }
                else{
                    dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000;
                }
            }
        }

        long answer = 0;
        for(int i=0; i<10; i++){
            answer+=dp[n][i];
        }
        System.out.println(answer % 1000000000);
    }
}

 

 

안 쉬운 계단 수..

 

 

2차원 배열로 dp를 표현한다.

 

dp[자리 수][앞에 오는 숫자] = 경우의 수 

 

0뒤에는 앞자리와 1 차이나는 숫자로써 올 수 있는 숫자가 1로 1개,

9뒤에는 8로 1개,

1~8은 2개이다.

 

이 점을 통해 세 가지 경우로 나누어서 동적계획법을 풀이한다.

 

 

 

일단 0으로 시작하는 수는 계단수가 될수 없으므로 앞에 오는 숫자로 0을 제외하고 경우의 수를 1로 초기화해준다.

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

 

 

 

앞에 오는 숫자가 0일 경우, 9일 경우, 1~8일 경우를 나눠 처리한다. 

for(int i=2; i<=n; i++){
    for(int j=0; j<10; j++){
        if(j==0){
            dp[i][j] = dp[i-1][j+1] % 1000000000;
        }
        else if(j==9){
            dp[i][j] = dp[i-1][j-1] % 1000000000;
        }
        else{
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000;
        }
    }
}

 

예를 들어 3자리 수 중 앞에 오는 숫자가 2인 경우에는,

(2자리수 중 맨앞 숫자가 1인 경우의 수) 와 (2자리 수 중 맨 앞 숫자가 3인 경우의 수) 를 더한 값이 되는 것이다. 

10, 12 두가지와 32, 34 두가지를 더한 네가지 경우가 된다. (210, 212, 232, 234) 

dp[3][2] = d[2][1] + dp[2][3]

 

 

 

마지막으로 n자리수의 모든 경우의 수를 더해준다. 

long answer = 0;
for(int i=0; i<10; i++){
    answer+=dp[n][i];
}