[백준저지] 10844번 : 쉬운 계단 수

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

1. 문제 

계단 수 -> 인접한 모든 자리수의 차이가 1이 나는 수

길이가 N인 계단 수가 몇 개?

 

입)

2

 

출)

17

 

2. 풀이 

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        long[][] D = new long[101][10];
        for (int i = 1; i < 101; i++) {
            for (int j = 0; j < 10; j++) {
                if (i == 1) {
                    if (j != 0) {
                        D[i][j] = 1;
                    }
                } else if (i == 2) {
                    if (j == 0) {
                        D[i][j] = D[i-1][j+1];
                    } else if (j == 1) {
                        D[i][j] = 1;
                    } else if (j == 9) {
                        D[i][j] = D[i-1][j-1];
                    } else {
                        D[i][j] = D[i-1][j-1] + D[i-1][j+1];
                    }
                } else {
                    if (j == 0) {
                        D[i][j] = D[i-1][j+1];
                    } else if (j == 9) {
                        D[i][j] = D[i-1][j-1];
                    } else {
                        D[i][j] = D[i-1][j-1] + D[i-1][j+1];
                    }
                }
                D[i][j] %= 1000000000;
            }
        }
        long result = 0;
        int N = sc.nextInt();
        for (int i = 1; i <= 9; i++) {
            result += D[N][i];
        }
        if (N > 1) {
            result += D[N][0];
        }
        System.out.println(result%1000000000);
    }
}

D[i][j] = 길이가 i이면서 마지막 숫자가 j인 계단 수의 총 개수

D[i][j] = D[i-1][j-1] + D[i-1][j+1] 

다이나믹 프로그래밍은 점화식을 세우는 것이 제일 중요

int, long 처리 주의

초기값 처리 주의