백준 11057 오르막 수

www.acmicpc.net/problem/11057

11057번: 오르막 수

#include <iostream>
using namespace std;

int arr[1001][10] = { 0, };



int main()
{
	int n;
	cin >> n;

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


	for (int i = 1; i < n+1; i++)
	{

		for (int j = 1; j < 10; j++)
		{
			arr[i][j] = (arr[i][j - 1] + arr[i - 1][j])% 10007;

		}
	}

	int ans = 1;
	for (int i = 1; i <= n; i++)
	{
		ans += arr[i][9];
	}

	cout << ans% 10007;
}

점화식을 찾기 그렇게 어려운 문제가 아니였다

간단히 생각해서 뒤에가 어떤 숫자로 끝나는지를 생각해보면 쉽게 풀 수 있는데, 

2자리에서 예시를 들때

ㅇㅇ 숫자에서 뒤가 1인경우 : 11

ㅇㅇ 숫자에서 뒤가 2인경우 : 12, 22

ㅇㅇ 숫자에서 뒤가 3인경우 : 13, 23, 33

 

3자리 숫자에서 볼때

ㅇㅇㅇ숫자에서 뒤가 1인경우 : 111

ㅇㅇㅇ숫자에서 뒤가 2인경우 : 112, 122, 222

ㅇㅇㅇ숫자에서 뒤가 3인경우 : 113, 123, 133, 223, 233, 333

 

그렇다면 배경색을 더하면 글자색이라는 결과가 도출이 가능해진다