[백준] 10844 쉬운 계단 수 - Dynamic Programming / Java

• 문제 링크

10844번: 쉬운 계단 수

 

• 풀이 과정

dp 배열을 2차원 배열로 정의하였으며, 이는 dp[자릿수][자릿값] 을 의미한다.

이때 오버플로우를 방지하기 위하여 long 형으로 정의한다.

 

이때 각 자릿값의 계단수를 구하는 코드는 dp[i - 1][j - 1] + dp[i - 1][j + 1] 이며,

예시로 dp[3][4] 이 주어질 때, 위의 코드를 적용하면 dp[2][3], dp[2][5] 가 구해지게 된다.

dp[3][4]	-	-	4
dp[2][3]	-	3	4
dp[2][5]	-	5	4

다만 자릿값이 0 일 경우 다음 자릿수의 값은 1 만 가능하고,

자릿값이 9 일 경우 다음 자릿수의 값은 8 만 가능하므로

위의 두 경우를 따로 분기를 둔다.

 

이렇게 구해진 모든 계단수의 개수를 합한 후, mod(1000000000) 를 곱하여 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        long mod = 1000000000;
        long[][] dp = new long[n + 1][10];

        for (int i = 1; i <= 9; 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][1] % mod;
                else if (j == 9)
                    dp[i][j] = dp[i - 1][8] % mod;
                else
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
            }
        }

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

        bw.write(res % mod + "\n");
        bw.flush();
    }

}