[동적계획법, 난이도 중하] 백준 11057번 오르막 수

만약 끝 자리 수가 j이라면, 다음 자리 수는 j부터 9까지 될 수 있다는 원리를 이용해 DP를 수행하면 되는 문제이다.

 

오르막 수의 길이가 1인 경우에는, 0부터 9까지 총 10개의 경우의 수가 있다.

즉 길이가 2일 때부터 DP를 수행해주면 되는데, 아래 표에서 설명할 것이다.

 

아래 표에서 행요소는 자릿수, 열요소는 수의 길이이다.

DP[i][j] = 길이가 i인 수에서 i번째 자리의 값이 j인 모든 경우의 수가 되는 것이다.

이 표를 이용하여 답을 구하려면, 각 열 안에 있는 모든 행 요소들을 전부 더하면 된다.

그 것을 아래 표에서는 SUM으로 표시하였다. 

 

 

최종 출력을 SUM에서 10007로 나눈 나머지값으로 해줘야 하기 때문에

N=7일 경우에는 답으로 11440가 되면 안되고, 1433이 되어야 한다.

오버플로우 방지용으로 갱신할 때마다 %10007 처리를 해주고,

행 요소들을 전부 더한 값도 %10007 처리를 해주면된다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <math.h>
#include <stack>
using namespace std;
long long dyn[1002][10];
int main() {
	int n;
	cin >> n;
	long long ans = 0;
	for (int i = 0; i < 10; i++) {
		dyn[1][i] = 1;
	}
	for (int i = 2; i < n + 1; i++) {
		dyn[i][0] = 1;
		for (int j = 1; j < 10; j++) {
			dyn[i][j] = (dyn[i][j - 1] + dyn[i - 1][j]) % 10007;
		}
	}
	for (int i = 0; i < 10; i++) {
		ans += dyn[n][i];
	}
	cout << ans%10007;
}