[백준 10844 java 자바] 쉬운 계단 수 (DP-이차원배열)

[Silver I] 쉬운 계단 수 - 10844

문제 링크

성능 요약

메모리: 14184 KB, 시간: 120 ms

분류

다이나믹 프로그래밍(dp)

---

풀이

dp인 것을 생각하는게 중요하고, 자연수의 자릿수에 대해 이해하는 것이 중요하다.
ex) 12345 자연수가 있으면, 배열 숫자로 [5][4][3][2][1] 로 표현한다.
2번째 자리에 올 수 있는 숫자는 [2][0]/[2][1].../[2][9] 이렇게 생각하면 된다. (오른쪽에서 왼쪽으로 [자연수 자릿수][올 수 있는 숫자])

나누는 숫자가 있는 경우, dp에 값을 넣을 때 마다, 나중에 결과를 제출할 때 또 mod로 나눠줘야한다.

코드

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

public class Main {
    static long mod = 1000000000;
    static int N;
    static long[][] dp; //[자연수 자릿수][0~9까지 오는 숫자]
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        dp = new long[N + 1][10];//1을 첫 idx로 사용하기 위해 [N+10], 첫자리 빼고 0~9까지 사용되므로 [10]

        for (int i = 1; i < 10; i++) { //1,2,3,4,5,6,7,8,9에 올 수 있는 가지수는 자기 자신 1개다.
            dp[1][i] = 1;
        }

        for (int i = 2; i <= N; i++) { 

            for (int j = 0; j < 10; j++) { //2번째 자리부터는 0-9까지 올 수 있다.

                if (j == 0) {//0과 9의 값에는 이전 자리수에 1, 8 한가지씩 경우밖에 없다.
                    dp[i][0] = dp[i - 1][1] % mod;
                } else if (j == 9) {
                    dp[i][9] = dp[i - 1][8] % mod;
                }
                else{
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod; //1~8까지는 경우가 두가지 ex)1인 경우 전 자리 수가 10 , 12 인 경우를 모두 더한다.
                }
            }
        }

        long result = 0;
        for (int i = 0; i < 10; i++) {
            result += dp[N][i];
        }
        System.out.println(result % mod);


    }
}