[백준 / C++] 11057번: 오르막 수 (dp, 다이나믹 프로그래밍)

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

11057번: 오르막 수

 

난이도: solved.ac 실버 1

 

알고리즘 분류

다이나믹 프로그래밍 (dp)

 

접근 방법

이어지는 숫자는 각 자리의 숫자보다 크거나 같아야 한다.

따라서 다음과 같은 규칙을 발견할 수 있다.

 

0으로 끝나려면 앞의 숫자는 0이어야 한다.

1로 끝나려면 앞의 숫자는 0 또는 1이어야 한다.

2로 끝나려면 앞의 숫자는 0 또는 1 또는 2여야 한다.

...

 

이를 점화식으로 표현하면 다음과 같다.

dp[n][i] = dp[n-1][0] + dp[n-1][1] + dp[n-1][2] + ... + dp[n-1][i]

(dp[n][i]: n번째 자리의 숫자가 i인 경우의 수)

 

구현

n = 1000이기 때문에 dp배열을 dp[1001][10]으로 해도 되지만 메모리를 좀이라도 더 줄이기 위해 dp[10]로만 만들었다.

이전의 경우의 수는 어차피 더해지므로 dp[9]부터 시작해 dp[0]까지 이전의 숫자에 덮어쓰는 식으로 구현했다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int dp[10];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, i, j, ans = 0;
	cin >> N;
	fill(dp, dp + 10, 1);
	while (--N) {
		for (i = 9; i >= 0; i--) {
			for (j = 0; j < i; j++) {
				dp[i] += dp[j];
			}
			dp[i] %= 10007;
		}
	}
	for (i = 0; i < 10; i++)
		ans += dp[i];
	cout << ans % 10007;
}

 

코드 제출 결과