[백준] 10844번_쉬운 계단 수(Java)

문제 풀이

백준의 10844번 문제입니다. 문제 출처

(1) 문제 파악

계단 수란 인접한 자리끼리의 차이가 모두 1인 수를 의미하며, 길이가 N인 계단 수의 개수를 찾는 문제입니다.

(2) 문제 풀이 방법 생각하기

0~9까지의 정수 중 0과 9를 주의해야 합니다.

• 0 다음에는 반드시 1이 옵니다 -> \(arr[N][0] = arr[N-1][1]\)
• 9 다음에는 반드시 8이 옵니다 -> \(arr[N][9] = arr[N-1][8]\)

0과 9를 제외한 수는 다음 자리에 자기 자신 -1과 +1한 값을 다음 수로 가질 수 있습니다.

\[arr[N][1] = arr[N-1][0] + arr[N-1][2]\]

이 규칙을 그대로 코드로 옮겨주면 됩니다!

(3) 시간 복잡도 확인

시간 제한은 2초 입니다. 즉, 대략 2억번 연산 안에 문제를 해결해야 합니다.

dp에 대한 계산을 위해 for문이 중첩되어 사용되지만 O(N*10) 이므로 O(N) 시간 복잡도를 가집니다.

(4) 구현

import java.io.*;

public class Main {
    static final long MOD = 1_000_000_000;

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

        for(int i=1; i<10; i++) {
            // 한 자리 수는 무조건 계단 수가 1개니까
            dp[1][i] = 1;
        }

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

        long result = 0;
        for(int i=0; i<10; i++) {
            result += dp[N][i];
        }
        System.out.println(result % MOD);

        br.close();
    }
}