[백준, 자바] 10844번 - 쉬운 계단 수

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

풀이

오르막 수랑 비슷한 거 같아서 진짜 혼자 풀려고 이 악물었던 문제렷다.
대충 아래처럼 표를 만들어서 점화식을 만들었다.

보아하지 좌측 대각선과 우측 대각선을 합해서 모듈러로 나누면 될 것 같다.

근데 문제가, 1은 본인보다 작은 수가 없어서 좌측 대각선에 값이 없고,
9는 본인보다 큰 수가 없어서 우측 대각선에 값이 없다.

일단 얼레벌떡 짜봤더니 2로 테스트한 결과가 맞았다!!!
근데? 1로 테스트하니 range Exception이 떴다.

내가 dp[2][0]까지 초기화를 했더니 1일때 최대 범위를 벗어난 것이다.

그래서 N == 1일 때 리턴할까 하다가 왠지 꼼수마냥 걸릴 것 같아서 로직을 재점검해보기로 했다.

얘가 문제네;; 1로 값이 들어가야 값이 제대로 나온단 말이다.
걍 dp[1][] 번째 초기화할 때 밑에 count[1]도 초기화를 했다.

int[] count = new int[N+1];

        for(int k = 1; k <= 9; k++) {
            dp[1][k] = 1;
        }
        count[1] = 9; // 첫째줄은 무조건 9개니까.

다만 이중 for문에서는 j의 범위를 1~9에서 0~9로 변경했다.
그리고 1과 9의 경우는 좌/우측 대각선 값을 일부러 더하지 않았다.

for (int j = 0; j <= 9; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i-1][j+1] % modular;
                } else if (j == 9) {
                    dp[i][j] = dp[i-1][j-1] % modular;
                } else {
                    dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % modular;
                }
                sum += dp[i][j];
            }

최종 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 1 <= N <= 100
        int modular = 1_000_000_000;
        long[][] dp = new long[N+1][10];

        int[] count = new int[N+1]; // 자릿수별로 count를 저장할 배열

        // 1번째 줄 초기화
        for(int k = 1; k <= 9; k++) {
            dp[1][k] = 1;
        }
        count[1] = 9; // 첫째줄은 무조건 9개니까.

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

        // 여기서 틀림. 각 dp의 자릿수를 모두 더해야 함. 
        for(int i = 0; i < 10; i++) {
            result += dp[N][i];
        }

        System.out.println(result % modular);
    }
}

틀린 코드
dp를 j 반복을 통해서 구했어도 각 dp[n]으로 접근하는 것이 아니라
dp[]의 모든 자리에 있는 수를 dp[n]까지 포함해서 다 더해야 하는 것이라고 한다.
아래로 짰다가 틀림.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 1 <= N <= 100
        int modular = 1_000_000_000;
        long[][] dp = new long[N+1][10];

        int[] count = new int[N+1]; // 자릿수별로 count를 저장할 배열

        // 1번째 줄 초기화
        for(int k = 1; k <= 9; k++) {
            dp[1][k] = 1;
        }
        count[1] = 9; // 첫째줄은 무조건 9개니까.

        for(int i = 2; i <= N; i++) {
            int sum = 0;
            for (int j = 0; j <= 9; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i-1][j+1] % modular;
                } else if (j == 9) {
                    dp[i][j] = dp[i-1][j-1] % modular;
                } else {
                    dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % modular;
                }
                sum += dp[i][j];
            }
            count[i] = sum % modular;
        }
        System.out.println(count[N]);
    }
}