[BOJ 10844] 쉬운 계단 수 (Java)

문제

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

10844번: 쉬운 계단 수

 

풀이

DP문제가 제일 어렵다. 

DP문제는 사고의 전환이 필요하다. 나한테 너무 어려운 부분...

어쨌든 해당 문제는 구글링을 통해 힌트를 조금 얻어서 풀었다. 

 

dp[i][j] = i자리수에서 j로 끝나는 계단수의 개수

N(자리수)가 1일 때

1, 2, 3, 4, 5, 6, 7, 8, 9

dp[1][0] = 0

dp[1][1] = 1, dp[1][2] = 1 ... dp[1][8] =1

dp[1][9] = 1

 

N이 2일 때 

10 / dp[2][0] = 1 

21 / dp[2][1] = 1

12, 32, / dp[2][2] = 2

23, 43, / dp[2][3] = 2

34, 54, / dp[2][4] = 2

45, 65, / dp[2][5] = 2

56, 76, / dp[2][6] = 2 

67, 87, / dp[2][7] = 2

78, 98, / dp[2][8] = 2

89 / dp[2][9] = 1

 

N이 3일 때

dp[3][0] = dp[2][1]

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

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

...

dp[3][9] = dp[2][8]

 

소스코드

package dp;

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

public class BOJ10844 {

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

        int[][] dp = new int[N+1][10];
        // dp[i][j] i는 자리수 j는 끝나는 숫자, 값은 i자리 수이면서 j로 끝나는 계단수 개수
        // dp[1][1~9] = 1개
        // dp[2][0] 10 : 1개
        // dp[2][1] 21 : 1개
        // dp[2][2] 12, 32 : 2개
        // ...
        // dp[1][8] 78, 98 : 2개
        // dp[2][9] 89 : 1개

        // dp[3][0]의 개수는? 2자리 수에서 0을 붙일 수 있는 숫자의 개수 dp[2][1]
        // dp[3][1]의 개수는? 2자리 수에서 1을 붙일 수 있는 숫자의 개수 dp[2][0] + dp[2][2]
        // dp[3][2] ? dp[2][1] + dp[2][3]
        // ...
        // dp[3][9]? dp[2][8]

        // 점화식 도출
        // j가 0이라면? dp[i][j] = dp[i-1][j+1]
        // j가 1~8이라면? dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
        // j가 9라면? dp[i][j] = dp[i-1][j-1]

        for(int i = 1; i <= N; i++){
            for(int j = 0; j <= 9; j++){
                if(i == 1 && j != 0){
                    dp[i][j] = 1;
                    continue;
                }
                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]%1000000000 + dp[i-1][j+1]%1000000000;
                }
            }
        }

        long count = 0;
        for(int j = 0; j <= 9; j++){
            count += dp[N][j];
        }

        System.out.println(count%1000000000);
    }
}