10844 쉬운 계단 수

시간이 없어서 후다닥 적습니다.

어떻게 풀어야할지 감이 잘 오지 않아 시간이 걸렸다.

 

 

N개의 숫자가 있다고 해보자.

N이 1일 경우는 1, 2, 3, 4, 5, 6, 7, 8, 9가 있다.

 

N이 2부터 경우가 생긴다.  계단 수 = 첫 숫자 -> 다음 숫자라고 표시해보면 다음과 같다.

1? = 1 -> 0

2? = 2 -> 1 or 3

3? = 3 -> 2 or 4

...

8? = 8 -> 7 or 9

9? = 9 -> 8

이렇게

1 ~ 8 다음에 오는 숫자는 i-1과 i+1 두 가지 경우가 올 수 있다.

9 다음에는 무조건 8이 오게된다.

* 두 번째 자리부터는 0이 올 수 있지만, 앞의 수가 0이라면 다음 수는 무조건 1만 오게된다.

 

DP[N][마지막 수]로 생각해보자.

마지막 수가 1 ~ 8일 경우 각각 i-1과 i+1로부터 분기되어 왔을것이다.

N이 2이고, 마지막 수가 2인 경우를 생각해보면 DP[2][2] = DP[1][1] + DP[1][3]가 된다. (1 -> 2, 3 -> 2)

점화식은 DP[i][k] = DP[i-1][k-1] + DP[i+1][k+1]이 된다.

i번째 계단 수의 k로 끝나는 숫자는, 이 전 계단 수에서 끝나는 숫자가 k-1과 k+1인 경우의 합이다.

 

마지막 수가 0과 9일 경우는, 이 전 숫자가 반드시 각각 1과 8이어야 하므로 DP[2][0] = DP[1][1], DP[2][9] = DP[1][8]이 될것이다.

점화식은 각각 DP[i][0] = DP[i-1][1],  DP[i][9] = DP[i-1][8]이 된다.

 

코드는 아래와 같다.

해당 문제에서는 길이가 N인 계단 수의 개수를 10억으로 나누어야했지만,

N이 100까지이므로 경우의 수가 너무 크게 나온다.

따라서 각 계산마다 10억으로 나누어주었다. (0, 9의 경우는 이 전 배열의 값이 그대로 들어오므로 나누지 않았음)

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

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

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

        int[][] dp = new int[N+1][10];    // [N개 수][계단 수의 끝자리 수] = N개 수에서 끝자리 수가 같은 개수

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

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

        int result =0;
        for (int j = 0; j <= 9; j++) {
            result = (result + dp[N][j]) % DIV_SIZE;
        }
        System.out.println(result);
    }
}