[백준] 쉬운 계단 수 (!) (10844번 JAVA) / 400 - 다이나믹 프로그래밍 1

[백준] 400 - 다이나믹 프로그래밍 1 : 쉬운 계단 수 (!) (10844번 JAVA)

---

[접근 방법]

메모이제이션 기법으로 사용할 배열 dp를 다음과 같은 2차원 배열로 구성해야 한다.

dp[수의 길이 : N][수의 일의 자리 수]

	// 길이가 N 이고, 일의 자리 숫자 0 ~ 9 임을 표시
        long[][] dp = new long[N+1][10];
        dp[1][0] = 0;
        dp[1][1] = 1; // 1
        dp[1][2] = 1; // 2
        dp[1][3] = 1; // 3
        dp[1][4] = 1; // 4
        dp[1][5] = 1; // 5
        dp[1][6] = 1; // 6
        dp[1][7] = 1; // 7
        dp[1][8] = 1; // 8
        dp[1][9] = 1; // 9

 

 

N = 3인 경우를 그림으로 표현해 보았다.

 

 

여기서 N = 2 인 경우에서 일의 자리가 0 과 9인 경우

N = 2가 끝자리가 0인 경우, N = 3 에서 끝자리는 1인 경우 뿐이다.

N = 2가 끝자리가 9인 경우, N = 3 에서 끝자리는 8인 경우 뿐이다.

 

이를 고려 하여 도출된 점화식은 다음과 같다.

 

dp[N][0] = dp[N-1][1]  // 이전 자리 수가 1인 경우
dp[N][9] = dp[N-1][8]  // 이전 자리 수가 8인 경우

dp[N][m] = dp[N-1][m-1] + dp[N-1][m+1]

(단, N >= 2 이고, 1<= m <=8)

---

[JAVA 코드]

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

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));

        // 1 <= N <= 100
        int N = Integer.parseInt(br.readLine());
        
        // 길이가 N 이고, 일의 자리 숫자 0 ~ 9 임을 표시
        long[][] dp = new long[N+1][10];
        dp[1][0] = 0;
        dp[1][1] = 1; // 1
        dp[1][2] = 1; // 2
        dp[1][3] = 1; // 3
        dp[1][4] = 1; // 4
        dp[1][5] = 1; // 5
        dp[1][6] = 1; // 6
        dp[1][7] = 1; // 7
        dp[1][8] = 1; // 8
        dp[1][9] = 1; // 9

        for(int i=2; i<=N; i++){
            dp[i][0] = (dp[i-1][1]) % 1_000_000_000; // 십의 자리가 1인 경우
            dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % 1_000_000_000;
            dp[i][2] = (dp[i-1][1] + dp[i-1][3]) % 1_000_000_000;
            dp[i][3] = (dp[i-1][2] + dp[i-1][4]) % 1_000_000_000;
            dp[i][4] = (dp[i-1][3] + dp[i-1][5]) % 1_000_000_000;
            dp[i][5] = (dp[i-1][4] + dp[i-1][6]) % 1_000_000_000;
            dp[i][6] = (dp[i-1][5] + dp[i-1][7]) % 1_000_000_000;
            dp[i][7] = (dp[i-1][6] + dp[i-1][8]) % 1_000_000_000;
            dp[i][8] = (dp[i-1][7] + dp[i-1][9]) % 1_000_000_000;
            dp[i][9] = (dp[i-1][8]) % 1_000_000_000; // 십의 자리가 8인 경우
            
        }
        long result = 0;
        for(int i=0; i<=9; i++){
            result += dp[N][i];
            result = result % 1_000_000_000;
        }

        bw.write(result + "\n");

        bw.flush();
        bw.close();
    }
}