[C++] BOJ 11057 오르막 수

 

 

 

 

문제 출처

백준 온라인 저지

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

11057번: 오르막 수

 

문제 

 

문제 입 / 출력

 

풀이

DP를 활용해서 푼다

i 는 오르막 수의 길이를 나타내고, j는 오르막수의 끝나는 수를 나타낼 경우

• dp[i][j] = dp[i - 1][0] + dp[i - 1][1] + … + dp[i - 1][j - 1] + dp[i - 1][j]

로 식을 사용해서 표현할 수 있다

 

코드

#include <iostream>

using namespace std;

int dp[1001][11];
const int mod = 10007;

int main() {
  int n;
  long long result = 0;
  cin >> n;

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

  for (int i = 2; i <= n; i++)
    for (int j = 0; j <= 9; j++)
      for (int k = 0; k <= j; k++) {
        dp[i][j] += dp[i - 1][k];
        dp[i][j] %= mod;
      }

  for (int i = 0; i <= 9; i++) {
    result += dp[n][i];
  }

  cout << result % mod << "\n";
}