C언어 백준 11057번 오르막 수

문제 풀이

오르막 수는 수의 자리가 자릿수가 증가할 때 오르는 수이다. 규칙을 파악하여 점화식을 세워야하는 문제이다.

 

우선 DP 배열을 어떻게 구성할 지 생각 해 보자.

DP[자릿수][숫자] = 개수 로 세울 수 있다. 몇 번째 자릿수인지, 해당 자릿수의 오는 숫자 0~9, 그리고 배열 안에 담긴 경우의 수가 몇 개인지이다.

 

아래 표에서 N-1번째와 N번째 자리만 보더라도 알 수 있다. N번째 자리에 올 수 있는 수는 N-1번째 자릿수보다 같거나 크면 가능하다. 따라서, 0이었다면 0~9가 올 수 있는 것이고, 이 경우의 수는 N-1번째 자릿수의 0~9에 해당하는 경우의 수를 모두 더하면 전체 값이 나온다.

 

즉, DP[N][0]=DP[N-1][0]+DP[N-1][1]+.....+DP[N-1][9]인 것을 알 수 있다.

N-1번째 자리	N번째 자리
0	00 01 ... 09
1
2
3
4
5
6
7
8
9

 

코드

#include <stdio.h>

int n;
int arr[1010][10]={0,};
int sum;

int main(void)
{
	scanf("%d",&n);
	
	for (int i=0; i<10; i++)
	{
		arr[1][i]=1;
	}
	
	for (int i=2; i<n+1; i++)
	{
		for (int j=0; j<10; j++)
		{
			for (int k=0; k<j+1; k++)
			{
				arr[i][j] += arr[i-1][k]%10007;
			}
		}
	}
	
	for(int i=0; i<10; i++)
	{
		sum+=arr[n][i]%10007;
	}
	
	printf("%d",sum%10007);
	

	return 0;
}