C++) 백준 10844번 풀이_쉬운 계단 수

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

10844번: 쉬운 계단 수

 

전체 합을 구하기 위해... 각 케이스의 점화식을 나눠서 계산 할 필요가 있다는 것을 

뼈저리게

ㄴ꼈다

 

9->0이 계단수가 될 수 없고

0->9로 만들 수 없다는 걸 첨부터 깨닫긴 했는데

 

이걸 어떻게 식으로 만들지를 몰라서 한참 헤멨음

 

결론은... 길이별 끝 자리수를 나눠서 계산해야 한다

 

 

n개의 숫자를 사용하는 수들 중에 맨 끝 자리가 1이 되려면

그 전자리수가 2나 0이여야 함.

 

121, 101, 321 ...

 

그러니까 결국 n-1개의 숫자를 사용할 때 맨 끝 자리수가 2였던 경우와 0이였던 경우의 수를 더하면

n개의 숫자를 사용할 때 맨 끝자리 수가 1일때의 경우의 수가 나옴.

 

S(n) = S(n,0) + S(n,1) + S(n,2) + ... + S(n,8) + S(n,9)

S(n) = S(n-1,1) + S(n-1,0) + S(n-1,2) + ... + S(n-1,7) + S(n-1,9) + S(n-1,8)

 

근데 여기서

S(n,1) = S(n-1,0) + S(n-1, 2)

같은 일반 수와는 달리

 

S(n,0) = S(n-1,1)

밖에 안 되고

 

S(n,9) = S(n-1, 8)

밖에 안 됨.

 

여기까지 도출은 쉬웠는데

그래서 얘네를 어떻게 하냐구요 ㅠ

-> 자릿수별/끝자리별을 나눠서 생각.

-> 2차원 배열을 만든다.

 

표로 보면

이렇게 됨.

 

이제 코드로 짜면 됩니다.

 

#include<stdio.h>
int main(void) {
	int i, j, cnt, res;
	int sum[101][10];

	scanf("%d", &cnt);
	
	sum[1][0] = 0;
	for (i = 1; i < 10; ++i)
	{
		sum[1][i] = 1;
	}

	for (i = 2; i <= cnt; ++i)
	{
		sum[i][0] = sum[i - 1][1] % 1000000000;
		for (j = 1; j < 9; ++j)
		{
			sum[i][j] = (sum[i - 1][j - 1] + sum[i - 1][j + 1]) % 1000000000;
		}
		sum[i][9] = sum[i - 1][8] % 1000000000;
	}
	
	res = 0;
	for (i = 0; i < 10; ++i)
	{
		res = (res + sum[cnt][i]) % 1000000000;
	}

	printf("%d", res);
}