백준 11057 C++ - 오르막 수

Intro

문제해결 및 소스코드

#include <iostream>

using namespace std;

/*
											<규칙>
				- 오르막 수는 각자리 숫자가 오름차순으로 이루어진 수다.
				- 수는 0으로 시작할 수 있다. ex) 0, 01, 001 ...
				- 인접한 수가 같아도 오름차순으로 친다. ex) 00, 011 ...

										  <문제해결>
				- 문제는 이해되었지만 방법이 떠오르지 않아 규칙을 찾기위해 몇개를 무작정 써보았다.

				길이가 1인 오르막수 : 0, 1, 2, 3, ... , 8, 9		=> 10개
				길이가 2인 오르막수 : 00, 01, 02, ... 88, 89, 99	=> 55개
				길이가 3인 오르막수 : 000, 001, ... , 899, 999		=> 220개

				- 첫번째로 생각했던것은 왼쪽자리수를 보고, 그것보다 크거나 같은수를 붙여주는것이었다.
				: 예를들어 0에는 0~9가 붙을수 있다.
				=> 이 방법은 너무 비효율적이라고 생각했다.

				- 두번째로, dp를 이용한 방법이다.
				: 길이가 2인 오르막수를 만들때 길이가 1인 오르막수를 이용하는 방법을 생각해봤다.

				먼저, 테이블을 설정했다. 1차원 배열로는 도저히 풀방법이 생각나지않아 2차원배열을 사용했다.
				dp[i][j] : 길이가 i(1~1000)이고, j(0~9)로 끝나는 오르막수의 갯수

				그렇다면 길이가 1이고 j로 끝나는 오르막수는 각 1개씩이라는 기저값이 설정된다.
				그리고, 길이에 상관없이 0으로 끝나는 오르막수는 0만있는 수, 즉 1개뿐이다.
				따라서 dp[1][0] ~ dp[1][9] = 1, dp[i][0] = 1로 설정된다.

				점화식을 찾기위해 몇개만 써보았다.
				
				dp[2][0] = 1
				dp[2][1] : 길이가2인 1로끝나는 오르막수 : 01, 11	=> 길이가 1이고 0으로끝나는 수, 길이가 1이고 1로끝나는 수에 1일붙인것.
				=> dp[2][1] = dp[1][0] + dp[1][1]
				
				dp[2][2] : 02, 12, 22	
				=> dp[2][2] = dp[1][0] + dp[1][1] + dp[1][2] = dp[2][1] + dp[1][2]

				dp[2][3] : 03, 13, 23, 33
				=> dp[2][3] = dp[1][0] + dp[1][1] + dp[1][2] + dp[1][3] = dp[2][2] + dp[1][3]

				따라서 dp[i][j] = dp[i-1][j] + dp[i][j-1]이 된다.
*/

int dp[1001][10] = { 0, };					// 길이가 i이고 j로 끝나는 오르막 수의 갯수

int main()
{
	int n;
	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++)
		{
			// 길이에 상관없이 끝자리가 0인 오르막수는 1개
			if (j == 0)
				dp[i][0] = 1;
			else
			{
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
				dp[i][j] %= 10007;
			}
		}
	}

	int sum = 0;

	// 길이가 n인 오르막수의 갯수
	for (int i = 0;i < 10;i++)
	{
		sum += dp[n][i];
	}

	cout << sum % 10007;
}