c언어 10844번 쉬운 계단 수 (백준)

#include <stdio.h>

long long int dp[102][11] = {0};

int main(void)
{   //자릿수 n = 2, 뒷자리가 0~9인 경우의 계단수
    dp[2][0] = 1;
    dp[2][1] = 1;
    dp[2][2] = 2;
    dp[2][3] = 2;
    dp[2][4] = 2;
    dp[2][5] = 2;
    dp[2][6] = 2;
    dp[2][7] = 2;
    dp[2][8] = 2;
    dp[2][9] = 1;

    int n = 0;
    scanf("%d", &n);
    if(n == 1) { //한 자릿수
    	printf("9");
    	return 0;
	}
    //결과값을 1000000000으로 나눠야 한다.
    for(int i = 3; i<=n; i++) //세자리수 이상 시, 구하기
    {
    	dp[i][0] += dp[i-1][1]; //끝이 0이면, 그 전의 자릿수는 1밖에 없다
    	if(dp[i][0] >= 100000000) dp[i][0] = dp[i][0] % 1000000000; //넘으면 나머지만
    	for(int j = 1; j<=8; j++)//끝이 1~8이면, 그 전의 자릿수는 끝보다 1 크거나 작은것이다.
    	{
    		dp[i][j] += dp[i-1][j-1] + dp[i-1][j+1];
    		if(dp[i][j] >= 100000000) dp[i][j] = dp[i][j] % 1000000000; //넘으면 나머지만
		}
    	dp[i][9] += dp[i-1][8]; //끝이 9이면, 그 전의 자릿수는 8밖에 없다
    	if(dp[i][9] >= 100000000) dp[i][9] = dp[i][9] % 1000000000; //넘으면 나머지만
	}
	
	long long int sum = 0;
	for(int i = 0; i<=9; i++) {
		sum += dp[n][i]; //0부터 9까지 더해준다.
		if(sum >= 1000000000) sum = sum%1000000000; //넘으면 나머지만
	}
	
	printf("%lld", sum); //출력
    return 0;
}

 

풀이 

자릿수와 관계없이 모든 계단 수의 끝에는 0~9만 올 수 있으며,

0 앞에는 반드시 1만

9 앞에는 반드시 8만

1~8 앞에는 반드시 거기서 +1, -1 값만 올 수 있다.

 

이를 통해서 구하고자 하는 자릿수까지 2자릿수에서 부터 구해서 올라오면 된다.

 

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수