[Java] 10844번: 쉬운 계단 수 Silver 1

문제 링크

이 문제는 보자마자 음~ 규칙 찾는 문제네~ 하면서 덤벼들었다가 곤욕을 치렀다..

이렇게 나름의 규칙이라고 발견은 했다.

끝자리가 0일 때와 9일 때 그 다음 차례에 안 되는 케이스가 하나씩 발생하기 때문에 1개씩 케이스가 덜 발생한다.

그런데 이게 개수가 뒤죽박죽이었다..

왜냐면 끝자리가 0이려면, 그 전의 자리가 1인 경우가 있고,
1로 끝나려면 앞자리가 0과 2일 때고, 0은 계속 순환되고,
2가 오려면 앞자리가 1과 3일 때도, 여기서 1이 또 순환되고,
도저히 이런 방식으로는 풀 수가 없었다~..

그래서 생각을 좀 해봤는데 표로 풀어야 겠다는 생각이 문득 들었다.

바로 이렇게 말이다.

보면 각 끝자리수는 인접한 두 수에 의해서 발생한다.

예를 들어 끝자리수 1은 인접한 수 0과 2에 의해서 발생한다.
그렇기에 이전 케이스의 0과 2의 경우의 수의 합이 되는 것이다.

그러나 끝에 위치한 0과 9는 오직 1과 8에 의해서만 만들어지기 때문에 바로 이전 케이스의 수가 된다.

그리고 이런 규칙이었기 때문에 그 수가 불규칙적이었던 것이다..

코드로 간단하기는 매우 간단했다!

정답

근데 바로 통과하지는 못 했다..

수의 범위가 금방 커져서 모든 위치에서 수를 나머지 연산자로 걸러줘야했는데, 그렇게 안 해서 몇 번 틀렸다 ㅠㅠ~..

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N 입력 받기
        int N = Integer.parseInt(br.readLine());

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

        }

        // 출력
        long ans = 0;
        for (int j = 0; j < 10; j++) {
            ans = (ans + dp[N - 1][j]) % 1000000000;
        }
        System.out.println(ans);
    }
}