[C++] BOJ / 11057번 / 오르막 수

11057번: 오르막 수

 

문제

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

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

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

입력

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

출력

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

풀이

길이가 1인 오르막 수의 개수는 0, 1, 2, ..., 9 까지 총 10가지 입니다.

 

다음으로 길이가 2인 오르막 수의 개수를 생각해보겠습니다.

길이가 1인 오르막 수 앞부분에 숫자를 이어붙이는 방식을 생각하시면 되겠습니다.

 

저희가 이어붙일 수 있는 숫자는 0부터 9까지 총 10가지가 있습니다. 그 중에서 0은 오르막 수의 모든 경우의 수에 이어 붙일 수 있습니다. 즉, (00, 01, 02, 03, ..., 09)의 경우를 말합니다.

다음으로 1은 1부터 9까지 총 9가지 경우의 수에 이어 붙일 수 있습니다. 즉, (11, 12, 13, ..., 19)의 경우를 말합니다.

마찬가지로 2는 2부터 9까지 총 8가지, 3은 3부터 9까지 총 7가지...

 

위의 예시를 통해 다음과 같은 점화식을 도출할 수 있습니다.

 

DP[2][0] = DP[1][0] + DP[1][1] + DP[1][2] + ... + DP[1][9]
DP[2][1] = DP[1][1] + DP[1][2] + DP[1][3] + ... + DP[1][9]
DP[2][2] = DP[1][2] + DP[1][3] + DP[1][4] + ... + DP[1][9]

...

 

여기서 DP[i][j]는 길이가 i인 오르막 수 중에서 가장 앞자리 숫자가 j인 수의 개수를 의미합니다.

 

해당 문제의 경우에도 나누기 연산을 지속적으로 수행해주어야 하며, long long 자료형을 이용하여야 합니다.

 

이번에도 제가 직접 메모장에 적으면서 풀이한 내용을 함께 첨부하겠습니다.

부족한 글 읽어주셔서 감사합니다.

 

---

#include <iostream>

using namespace std;

#define MAX 1000
#define MOD 10007
#define ll long long
#define endl '\n'

ll DP[MAX + 1][10];

int main()
{
	int n, ans = 0;

	cin >> n;

	for (int i = 0; i < 10; ++i)
		DP[1][i] = 1;

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

	for (int i = 0; i < 10; ++i)
		ans = (ans + DP[n][i]) % MOD;

	cout << ans << endl;
}