21.07.13 - [BOJ] 10844. 쉬운 계단 수

[suhyunsim]

문제

• 쉬운 계단 수

핵심 아이디어

• 계단 수: 인접한 자리의 차이가 1이 나는 수
• D[i][j] = 길이가 i인 계단수 마지막 자리가 j인 개수
  • D[i][j] = D[i - 1][j- 1] + D[i -1][j + 1] (1 <= j <=8)
  • j가 0이라면? j+1만 올 수 있음
  • j가 9라면? j-1만 올 수 있음
• D[1][1] ~ D[1][9] -> 1
• D[1][0] = 0 (조건 때문)

어려운 점, 실수

풀이

package main.java.com.poogle.BOJ.Q10844;

import java.util.Scanner;

public class Main {
    static final long MOD = 1000000000L;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[][] d = new long[n + 1][11];
        for (int i = 1; i <= 9; i++) {
            d[1][i] = 1;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= 9; j++) {
                d[i][j] = 0;
                if (j - 1 >= 0) {
                    d[i][j] += d[i - 1][j - 1];
                }
                if (j + 1 <= 9) {
                    d[i][j] += d[i - 1][j + 1];
                }
                d[i][j] %= MOD;
            }
        }
        long ans = 0;
        for (int i = 0; i <= 9; i++) {
            ans += d[n][i];
        }
        ans %= MOD;
        System.out.println(ans);
    }
}