백준 10844번 쉬운 계단 수 dp 풀이

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

10844번: 쉬운 계단 수

arr[N][L] = arr[N - 1][L - 1] + arr[N - 1][L + 1]=> 길이가 N 일 때, 마지막 수가 L일 경우의 계단 수

주의할 점은 위의 점화식은 L이 (1 ~ 8) 일 때 성립한다.

왜냐하면 0은 +1을 한 1만 허용되고 9는 -1을 한 8만 적용되기 때문이다.

구체적인 점화식은 다음과 같다.

L = 0 => dp[N][L] = dp[N - 1][L + 1]

L = (1 ~ 8) => arr[N][L] = arr[N - 1][L - 1] + arr[N - 1][L + 1]

L = 9 => dp[N][L] = dp[N - 1][L - 1]

코드로 풀이하면 다음과 같다.

import java.io.*;

public class t10844 {

  static int mod = 1000000000;
  static long[][] arr;
  static long result;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
    arr = new long[100][9];

    for (int i = 0; i < 9; i++) {
      arr[0][i] = 1;

      if (i == 8) {
        arr[1][i] = 1;
      } else {
        arr[1][i] = 2;
      }
    }
    dp(N);
    bw.write(result % mod + "");

    br.close();
    bw.flush();
    bw.close();
  }

  private static long dp(int n) {
    result = 0;
    if (n > 2) {
      for (int i = 2; i < n; i++) {
        for (int j = 0; j < 9; j++) {
          if (j == 0) {
            arr[i][j] = (arr[i - 2][j] + arr[i - 1][j + 1] % mod);
          } else if (j == 8) {
            arr[i][j] = (arr[i - 1][j - 1]) % mod;
          } else {
            arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j + 1]) % mod;
          }
        }
      }
    }
    for (int i = 0; i < 9; i++) {
      result += arr[n - 1][i];
    }
    return result;
  }
}