[10844] 쉬운 계단 수

✔ 쉬운 계단 수

[백준 10844]

문제 분석하기

N번째의 길이에서 i로 끝나는 계단 수가 있었을 때 이 계단 수의 N - 1의 자리에 올 수 있는 수는 i - 1, i + 1인 것을 가지고 문제에 접근

손으로 풀어보기

1. 점화식의 형태와 의미를 도출
   • D[N][H]는 길이가 N인 계단에서 H 높이로 종료되는 계단 수를 만들 수 있는 경우의 수
2. 점화식을 구함
   • N에서 계단 높이가 0일 때 계단 수가 되려면 N - 1에서는 높이가 1이어야 하므로 D[i][H] = D[i - 1][H + 1]
   • N에서 계단 높이가 9일 때 계단 수가 되려면 N - 1에서는 높이가 8이어야 하므로 D[i][H] = D[i - 1][H - 1]
   • 나머지는 가운데 계단이므로 양쪽 계단에서 계단 수를 만들 수 있으므로 D[i][H] = D[i - 1][H - 1] + D[i - 1][H + 1]
3. 점화식으로 D 배열을 채운 후 D[N][0] ~ D[N][9]의 모든 값을 더한 값을 출력

슈도코드 작성하기

D[N][H](길이가 N일 때 높이 H로 끝나는 계단 수의 모든 경우의 수)
for(i -> 1 ~ N) {
    D[1][i] = 1
}
for(i -> 2 ~ N) {
    D[i][0] = D[i - 1][1]
    D[i][9] = D[i - 1][8]
    for(j -> 1 ~ 8) {
        D[i][j] = D[i - 1][j - 1] + D[i - 1][j + 1]
        나온 결과를 1000000000 나머지 연산 수행하기
    }
}
sum(결괏값)
for(i -> 0 ~ 9) {
    sum에 D[N][i]의 값을 모두 더하기
}
sum 출력하기

코드 구현하기

/**
 * 10844) 쉬운_계단_수
 */
public class D088_10844 {
    static int N;
    static long mod = 1000000000;
    static long D[][];
    static long sum;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        // D[N][H](길이가 N일 때 높이 H로 끝나는 계단 수의 모든 경우의 수)
        D = new long[N + 1][11];
        // 길이가 1일 때 만드는 높이 H로 끝나는 계단 수의 모든 경우의 수는 1
        for (int i = 1; i <= 9; i++) {
            D[1][i] = 1;
        }
        for (int i = 2; i <= N; i++) {
            // N에서 높이가 0이면 N - 1에서 높이가 1이어야 계단 수가 가능
            D[i][0] = D[i - 1][1];
            // N에서 높이가 9이면 N - 1에서 높이가 8이어야 계단 수가 가능
            D[i][9] = D[i - 1][8];
            // 높이가 1 ~ 8이면서 N - 1에서 자신보다 한 단계 위 또는 한 단계 아래 높이에서 올 수 있음
            for (int j = 1; j <= 8; j++) {
                D[i][j] = (D[i - 1][j - 1] + D[i - 1][j + 1]) % mod;
            }
        }
        // sum(결괏값)
        sum = 0;
        // sum에 D[N][i]의 값을 모두 더하기
        for (int i = 0; i < 10; i++) {
            sum = (sum + D[N][i]) % mod;
        }
        // sum 출력하기
        System.out.println(sum);
    }
}