[백준/C++] 오르막 수

오르막 수

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력 첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력 첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

1

예제 출력 1

10

풀이

특정 위치에서 그 앞의 수보다 더 크거나 같은 수를 이어붙이는 경우의 수를 구하라는 subcase를 두면 이 문제는 subcase들의 합으로 나타낼 수 있으므로 최적부분구조이고 특정 숫자로 끝났을 때 다음에 올 수 있는 경우의 수가 정해져있고 이가 반복되므로 반복문제이며 이는 곧 DP로 풀 수 있다는 의미이다.

이전에 풀었던 문제들과 마찬가지로 현재 고를 수 있는 숫자가 바로 직전에 온 수에 의존하기 때문에 위치를 표시하는 매개변수 하나만 가지고는 충분하지 않고 마지막에 온 숫자를 매개변수로 더 주어야 점화식을 세울 수 있다.

D[i][k] = D[i][k] + D[i - 1][j], j는 k보다 작거나 같은 수

#include <iostream>
#define MOD 10007
using namespace std;

int D[1001][10] = {0};

int main()
{
	int N;
	cin >> N;
	
	for (int i = 0; i < 10; ++i)
		D[1][i] = 1;

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

	int num = 0;
	for (int i = 0; i < 10; ++i)
		num = (num + D[N][i]) % MOD;

	cout << num;
	return 0;
}

끝