[TIL] 막혔던 문제 - 백준 10844번 풀이

1. 막히게 된 문제

날마다 백준 실버 ~ 골드 티어의 문제를 풀던 도중 오늘은 어떻게 풀이해야 할 지 감이 안오는 문제를 발견했습니다

• 백준 10844번 - 쉬운 계단 수

처음에는 첫 자리부터 자릿수를 넘길 때마다 + 또는 -가 되니 9 * 2^(자릿수-1)으로 해야하나 싶었는데
이러면 각 자릿수에서 9를 초과하거나 0보다 낮아지는 경우의 예외를 계산하기가 너무 어렵더라구요

전혀 갈피를 못 잡고 있는 채, 결국 질문 게시판에 있는 다른 사람들의 질문이 담긴 코드를 확인해보았습니다

• 10844번 - 쉬운 계단 수 / Q. 틀린 이유를 모르겠습니다.

2. 다른 사람의 풀이를 참고해보면…

Integer[][] dp = new Integer[101][10];  // dp[자릿수][끝나는 수]
dp[1] = new Integer[]{0, 1, 1, 1, 1, 1, 1, 1, 1};

for (int i=2; i<N+1; i++) {
    for (int j=0; j<10; j++) {
        if (j==0)
            dp[i][j] = dp[i-1][1];
        else if (j==9)
            dp[i][j] = dp[i-1][8];
        else
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];
        
        dp[i][j] = dp[i][j] % 1_000_000_000;
    }
}

Integer answer = 0;
for (Integer a : dp[N]) answer += a;

천천히 머릿속으로 시뮬레이션을 돌려본 결과… 의외로 단순하게 생각해서 풀어야 했던 문제였습니다
이전에 반드시 이런 풀이는 공식이 있을 것이라 믿었는데 이중 for문으로 경우의 수를 구해야 됐었네요

3. 문제 풀이

처음 dp[1]에는 각각의 경우의 수가 담긴 배열 {0, 1, 1, 1, 1, 1, 1, 1, 1, 1}가 담깁니다
// 0으로 시작할 수 없으니 제외

그리고 N = 2일 경우, dp[2]에는 이전 배열의 +1과 -1 두 개에 위치한 값의 경우의 수를 더합니다
이때, 숫자가 0이 되는 경우와 9가 되는 경우는 각각 1에서 0으로, 8에서 9로 가는 경우만 있으니 따로 계산해줍니다

마지막 for문으로 마지막에 올 수 있는 각 자릿수의 경우의 수를 더하면서
조건에 따라 값을 1,000,000,000으로 나눠주는 작업을 합니다

이때, answer에 더해지는 각 자릿수의 합에도 1,000,000,000을 나눠주는 작업을 추가해주면 됩니다

import java.io.*;

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

        // dp[자릿수][0~9로 끝나는 경우의 수]
        int[][] dp = new int[101][10];
        dp[1] = new int[] {0, 1, 1, 1, 1, 1, 1, 1, 1, 1};

        for (int i = 2; i < N+1; i++) {
            for (int j=0; j<10; j++) {
                if (j == 0)
                    dp[i][j] = dp[i-1][1];
                else if (j == 9)
                    dp[i][j] = dp[i-1][8];
                else
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];

                dp[i][j] %= 1_000_000_000;
            }
        }

        // (마지막 자릿수의 경우의 수 합계 % 1,000_000,000) 출력
        int answer = 0;
        for (int a : dp[N]) answer = (answer + a) % 1_000_000_000;

        bw.write(answer+"\n");
        bw.flush();

        br.close();
        bw.close();
    }
}