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

 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력하는 문제이다.

 

문제 해결 방법

1. 오르막 수의 길의 별로 오르막 수를 구한다.

 

N이 1이면

 

총 오르막 개수는 총 10개이다. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

 

N이 2일 때 각 숫자별로 보겠다.

 

만약 00은 불가능하니 PASS

01은 불가능 , 11은 가능 앞으로 앞이 0인 경우는 보지 않는다.

 

12, 22 가능

 

13, 23, 33 가능

이런 느낌으로 자기보다 작은 이전 index의 숫자들을 탐색하면 된다.

 

#include <iostream>

using namespace std;

int DP[1001][10];

int main(void)
{
	int N=0;
	
	cin>>N;
	
	for(int i=0; i<=9; i++)
	{
		DP[1][i]=1;
	}
	
	for(int i=2; i<=N; i++)
	{
		for(int j=0; j<=9; j++)
		{
			for(int k=1; k<=j; k++)
			{
				DP[i][j]=(DP[i][j]+DP[i-1][k])%10007;
			}
		}
	}
	
	int sum=0;
	
	for(int i=1; i<=N; i++)
	{
		for(int j=0; j<=9; j++)
		{
			sum+=DP[i][j]%10007;
		}
	}
	
	
	
	cout<<sum%10007;
	
	
	return 0;
}