백준 Baekjoon 11057 오르막 수 풀이

사용언어

Visual studio 2019 C++

생각하기

다이나믹 프로그래밍

[11057 풀이]

#include <iostream>

#define endl "\n"
#define MAX 1001
#define MOD 10007
using namespace std;

int N;
int dp[MAX][10];

void init() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

int main() {
	init();
	cin >> N;

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

	for (int i = 2; i <= N; i++) {
		dp[i][0] = 1;
		for (int j = 1; j < 10; j++)
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
	}

	int result = 0;
	for (int i = 0; i < 10; i++)
		result += dp[N][i];

	result %= MOD;
	cout << result << endl;
}