C언어 백준 10844번 쉬운 계단 수

문제 풀이

계단 수는 자리 차이마다 1의 차이를 가지고 있는 수이다.

DP에서 중요한 점은 배열로 풀 때

- DP의 인덱스는 어떤 값을 넣을 것이고

- 그 배열 안에는 어떤 값이 들어갈 지

- 점화식을 어떻게 세울 것인지

인 것 같다.

이번 문제도 마찬가지로 인덱스 값을 어떤 값을 넣지와 배열 안의 값이 어떤 값이 들어갈 지가 중요하였다.

 

DP[몇 번째 수][자릿수] = 총 개수 로 정의할 수 있다.

이 때, 바로 옆 숫자 대비 1씩 다르다. 왼쪽부터 n번째 자릿수는 n-1번째 자릿수 값+1과 n-1번째 자릿수 값-1의 개수에서 오기 때문에 둘을 더하면 된다. 예를 들어 3번째 자릿수 3인 경우, 2번째 숫자 2의 개수와 2번째 숫자 4의 개수를 더한 개수가 된다.

다만, 0과 9는 올 수 있는 경우가 이전 자릿수에서 1과 8에서만 올 수 있기 때문에 예외처리한다.

 

코드

#include <stdio.h>

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

int main(void)
{
	scanf("%d",&n);
	for (int i=1; i<10; i++)
	{
		arr[1][i]=1;
	}
	arr[1][0]=0;
	
	for (int i=2; i<n+1; i++)
	{
		for(int j=0; j<10; j++) // 자리수 
		{
			if (j==0)
			{
				arr[i][j]=arr[i-1][1];
			}
			else if (j==9)
			{
				arr[i][j]=arr[i-1][8];
			}
			else
			{
				arr[i][j]=(arr[i-1][j-1]+arr[i-1][j+1])%1000000000;
			}
		}
	}
	
	for (int i=0; i<10; i++)
	{
		sum=(sum+arr[n][i])%1000000000;
	}
	printf("%d",sum);
}