코드 복사/붙여넣기 하는 당신이 아름답습니다.

11057 : 오르막 수

풀이

점화식을 세우자!

dp[수열의 자릿수 i][i번째 자릿수의 숫자 j] 일 때의 경우의 수

dp[i][j] = dp[i-1][j] + dp[i][j-1]

코드

#include <stdio.h>

const int mod = 10007;
int n, i, j, ans, dp[10001][10];

int main() {
	scanf("%d", &n);
	for (i = 0; i <= 9; i++) dp[1][i] = 1;
	for (i = 2; i <= n; i++) {
		dp[i][0] = dp[i - 1][0];
		for (j = 1; j <= 9; j++) {
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
		}
	}
	for (i = 0; i <= 9; i++) {
		ans = (ans + dp[n][i]) % mod;
	}
	printf("%d", ans);
	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge

wookje.kwon's profile image

wookje.kwon

2017-04-18 13:13

Read more posts by this author