[c++ 백준] (11057번) 오르막 수

문제

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

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

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

입력

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

출력

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

---

풀이과정

 

1. dp를 이용하여 문제를 해결했습니다.

2. 기본적으로 크기가 10인 배열을 선언하여 숫자마다 올 수 있는 경우에 수를 대입 하였습니다.

3. 각 자리수 마다 다음 숫자에 대한 경우에 수를 더해 주었습니다.

(0의 자리 수 부터 시작 할 수 있기 때문에 0으로 시작하는 수도 계산)

0시작	1시작	2시작	3시작	4시작	5시작	6시작	7시작	8시작	9시작
1	1	1	1	1	1	1	1	1	1
10	9	8	7	6	5	4	3	2	1
55	45	36	28	21	15	10	6	3	1

4. 반복문을 N - 1 돌린 후 결과를 더하여 경우의 수를 구했습니다.

 

---

코드

#include<iostream>

#define endl "\n"
using namespace std;

#define MOD 10007
int N;
int dp[10];

void Answer()
{
	cin >> N;
	for (int i = 0; i < 10; i++)
		dp[i] = 1;
	for (int i = 0; i < N - 1; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			for (int k = j + 1; k < 10; k++)
			{
				dp[j] += dp[k];
			}
			dp[j] %= MOD;
		}
	}
	int result = 0;
	for (int i = 0; i < 10; i++)
		result += dp[i];
	cout << result % MOD;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	Answer();
	return 0;
}