본문으로 바로가기

길이가 n이고 마지막 수가 i인 계단 수는 길이가 (n-1)이고 마지막 수가 (i-1)인 수와 길이가 (n-1)이고 마지막 수가 (i+1)인 계단 수의 합과 같다.

#include <cstdio>

const int MOD = 1000000000;

int dp[101][10];
int n;
long long ans;

int f(int, int);// 길이가 n이고 마지막 수가 i인 계단 수

int main() {
  scanf("%d", &n);
  for (int i=1; i<=9; i++) {
    dp[1][i] = 1;
  }
  for (int i=0; i<=9; i++) {
    ans += f(n, i);
  }
  printf("%lld\n", ans % MOD);
  return 0;
}

int f(int n, int i) {
  if (i < 0 || i > 9) return 0;
  if (n == 1 && i == 0) return 0;
  if (dp[n][i]) return dp[n][i];

  // 길이가 n이고 마지막 수가 i인 계단 수는
  // 길이가 (n-1)이고 마지막 수가 (i-1)인 계단 수 +
  // 길이가 (n-1)이고 마지막 수가 (i+1)인 계단 수
  return dp[n][i] = (f(n-1, i-1) + f(n-1, i+1)) % MOD;
}

'Programming > Baekjoon Online Judge' 카테고리의 다른 글

[BOJ] 2193: 이친수  (0) 2018.05.15
[BOJ] 11057: 오르막 수  (0) 2018.05.15
[BOJ] 10844: 쉬운 계단 수  (0) 2018.05.15
[BOJ] 11052: 붕어빵 판매하기  (0) 2018.05.15
[BOJ] 9095: 1, 2, 3 더하기  (0) 2018.05.15
[BOJ] 11727: 2xn 타일링 2  (0) 2018.05.15

댓글을 달아 주세요