본문으로 바로가기

길이가 n이고 마지막 수가 i인 오르막 수의 개수는 길이가 (n-1)이고 마지막 수가 i보다 같거나 작은 수들의 개수의 합이다.

#include <cstdio>

int dp[1001][10];
int n;
int ans;

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

int main() {
  scanf("%d", &n);

  for (int i=0; i<=9; i++) {
    ans += f(n, i) % 10007;
  }

  printf("%d\n", ans % 10007);
  return 0;
}

int f(int n, int i) {
  if (n == 1) return 1;
  if (dp[n][i]) return dp[n][i];

  // 길이가 n이고 마지막 수가 i인 오르막 수의 개수는
  // 길이가 (n-1)이고 마지막 수가  i보다 같거나 작은 수들의 개수의 합이다 
  for (int j=0; j<=i; j++) {
    dp[n][i] += f(n-1, j) % 10007;
  }
  return dp[n][i] %= 10007;
}

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

[BOJ] 9465: 스티커  (0) 2018.05.15
[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

댓글을 달아 주세요