[BOJ] 10844: 쉬운 계단 수 (JAVA)

문제

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

 

여담

저번에 풀려고 시도했다가 풀지 못해서 그냥 나뒀던 문제였다.. 그치만 계속 외면할 수는 없어서 풀이를 참고해서 풀었다.

표를 그려서 풀었다면 규칙을 찾아낼 수 있었을텐데 계속 다른 방식으로 삽질해서 아쉬웠다😂 DP 오랜만에 푸니까 너무 어렵다..!!

 

풀이

이 문제는 규칙만 찾아내면 쉽게 풀이할 수 있다. 참고한 블로그의 표를 보고 쉽게 이해했으므로, 나도 표를 이용해서 설명하려고 한다.

해당 문제는 인접한 모든 자리의 차이가 1이다. 따라서 0에서 9까지의 숫자 뒤에 올 수 있는 숫자들의 특징은 다음과 같다.

• 앞의 자리가 0 ⇒ 다음 자리는 무조건 1
• 앞의 자리가 9 ⇒ 다음 자리는 무조건 8
• 앞의 자리가 1 ⇒ 다음 자리는 0 또는 2
• 앞의 자리가 2 ⇒ 다음 자리는 1 또는 3
• ...

이러한 성질을 고려해서 만들어질 수 있는 수를 표로 표현하면 다음과 같다. 이때, 0으로 시작하는 수는 만들 수 없지만, 점화식을 위해 잠시 포함시켜 놓고 최종 답을 계산할 때 제외하면 된다.

 

표를 통해 다음과 같은 특징을 가지고 있다는 것을 알 수 있다.

• 길이가 i이고 0으로 시작하는 수
  • dp[i][0] = dp[i-1][1]
• 길이가 i이고 j로 시작하는 수(1 ≤ j ≤ 8)
  • dp[i][j] = dp[i-1][j-1] + dp[i-][j+1]
• 길이가 i이고 9로 시작하는 수
  • dp[i][9] = dp[i-1][8]

 

코드

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

public class Main {
    static final long 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 + 1][10];
        // 한 자리수일 때는 모두 1로 초기화
        for (int i = 0; i <= 9; i++) {
            dp[1][i] = 1;
        }

        // 두 자리수 ~ N 자리수
        for (int i = 2; i <= n; i++) {
            // 오버플로우 방지를 위해 MOD로 나눈 뒤 저장
            dp[i][0] = dp[i - 1][1] % MOD; // 0은 뒤에 1만 올 수 있음

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

            dp[i][9] = dp[i - 1][8] % MOD; // 9는 뒤에 8만 올 수 있음
        }

        long total = 0;
        for (int i = 1; i <= 9; i++) {
            total = (total + dp[n][i]) % MOD;
        }
        System.out.println(total);
    }
}

---

참고

https://iseunghan.tistory.com/343