[백준/10844] 쉬운 계단 수 (Java/코드)

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

---

쉬운 계단 수 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	31939	9630	7014	28.384%

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

---

import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long sum=0;
        long[][] d = new long[101][11];
 
        for(int x=1; x<=9;x++){
            d[1][x] = 1;
        }
        // 규칙 d[n][k] = d[n-1][k+1] + d[n-1][k-1];
        for(int i =2; i<=n ; i++){
             d[i][0] = d[i - 1][1];
            for(int l=1 ; l<=9 ; l++){
                d[i][l] = (d[i-1][l+1] + d[i-1][l-1])% 1000000000;
            }
        }
        
        for(int x=0; x<10;x++){
            sum = sum + d[n][x];
        }        
        System.out.println(sum% 1000000000);
    }
}
 

어려웠던게, 

1. 배열 0 을 기준으로 잡고 해버려서 실제 계산하는 값과 헷갈렷다

2. d[i][0] 초기화를 단순히 1 로 잡아버렸는데 실제 0은 맨 앞에만 못오는 것 뿐, 뒤에는 올수 있으므로

   d[n][k] = d[n-1][k-1] + d[n-1][k+1] 의 점화식에 맞춰, 

   d[n-1][k-1]은 -1 이므로 안되고 d[n-1][k+1]은 1이므로 1에서 0 or 2 범위에 counting 되므로 초기화를 d[i][0]= d[i-1][1]; 로 잡아준다.

3. 100보다 작거나 자연수라고 했으므로, 배열의 범위를 줄이기 위해 long[n+1][11]이 아닌 long[101][11]로 fix 해준다.