[DP] BOJ 11057번 오르막 수

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

11057번: 오르막 수

- 문제파악

정수 N이 주어지고 수의 자리가 오름차 순인 N자리 수를 만들 수 있는 경우의 수를 출력하라

 

- 정답

이런 문제 이전에 계속 당해서 조금 생각하니 풀렸다.

D[i][j]를 선언했다 i는 자리수 j는 마지막에 오는 수의 경우의 수이다.

예를 들어 i =2 이고 j =3  이면 3이 마지막으로 오는 오르막 수를 만드는 경우의 수는 D[2][3]이다.

 

N = 1일때가 초항으로 1자리 수는 자기 자신만 가졌을 때 오름차순 이므로 10개이다 (0~9)

j가 0 일때는 0이 N 자리 모두 채웠을 때 밖에 존재하지 않는다, (0, 00, 000, ...)

점화식은 아래와 같다.

 

D[i][j] += (D[i - 1][j] + D[i][j - 1])

1. 이전 자리수(i-1)에서 자기 자신(j)이 마지막으로 오는 경우에 마지막에 다시 자기 자신이 와도 오름차순이다.

2. 현재 자리수(i)에서 자기 자신 이전에 수(j-1)가 오는 경우의 수는 자기 자신도 같은 경우의 수를 가질 수 있다.

 

ex 1)

i = 2 , j = 3

03 13 23

 

i = 3 , j = 3

033 133 233 <- 오름차순 성립

 

ex 2)

i = 3, j = 2

002 012 112 122 222

 

i = 3 , j = 3

003 013 113 123 223 <- 오름차순 성립

 

 

#include "bits/stdc++.h"

using namespace std;

int n;
unsigned long long D[1002][10];
unsigned long long ans;

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;

	fill(D[1], D[1] + 10, 1);

	for (int j = 2; j <= n; j++)
	{
		D[j][0] = 1;
		for (int i = 1; i < 10; i++)
		{
			D[j][i] += (D[j - 1][i] + D[j][i - 1]) % 10007;
		}
	}

	for (int i = 0; i < 10; i++)
	{
		ans += D[n][i] % 10007;
	}

	cout << ans % 10007;

}