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

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

 

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

---

1.  아이디어

 

다이나믹 프로그래밍을 활용하면 간단하게 해결할 수 있다.

---

2. 문제풀이

 

dp 배열을 2차원 배열로 선언했다. 행은 자리수, 열은 해당 자리수에 온 숫자와 매핑시켜서 가능한 경우의 수를 저장했다.

계단 수는 현재 자리에 0이 오는 경우, 9가 오는 경우, 나머지 숫자가 오는 경우로 나눌 수 있고 0이 오는 경우는 앞 자리 수가 1인 경우, 9가 오는 경우는 앞자리 수가 8인 경우, 나머지 숫자 N이 오는 경우는 앞 자리 수가 N-1 또는 N+1인 경우다.

이를 2중 for문을 통해 갱신하며 저장시켰고 중간에 1,000,000,000으로 나누어서 오버플로우를 방지하려고 했다. 그럼에도 오버플로우가 발생하기 쉬워서 dp 배열도 long 타입으로 선언했다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {

    private static final int MOD = 1_000_000_000;

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

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

        long[][] dp = new long[N][10];
        Arrays.fill(dp[0], 1);
        dp[0][0] = 0;

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

        long ans = 0;
        for (int i = 0; i < 10; i++) {
            ans += dp[N - 1][i];
            ans %= MOD;
        }

        System.out.println(ans);
    }
}

---

4. 후기