[BOJ] 10844 쉬운 계단수 - 동적 계획법

N자리 계단수에 대해

끝자리가 1 - N-1자리 계단수의 끝자리가 0,2 

끝자리가 2 - N-1자리 계단수의 끝자리가 1,3 

끝자리가 3 - N-1자리 계단수의 끝자리가 2,4 

끝자리가 4 - N-1자리 계단수의 끝자리가 3,5 

끝자리가 5 - N-1자리 계단수의 끝자리가 4,6 

끝자리가 6 - N-1자리 계단수의 끝자리가 5,7 

끝자리가 7 - N-1자리 계단수의 끝자리가 6,8 

끝자리가 8 - N-1자리 계단수의 끝자리가 7,9 

끝자리가 9 - N-1자리 계단수의 끝자리가 8 

끝자리가 0 - N-1자리 계단수의 끝자리가 1 

 

모듈러 연산은 합에대한 분배법칙이 성립함에 유의하면 쉽게 풀어낼 수 있는 문제이다.

#include <iostream>

unsigned long long LastNumberCounts[101][10];

int main()
{

	int N;

	std::cin >> N;

	LastNumberCounts[1][0] = 0;
	for (int i = 2; i < 10; ++i) LastNumberCounts[1][i] = 1;

	for (int i = 2; i <= N; ++i)
	{
		LastNumberCounts[i][0] =	LastNumberCounts[i - 1][1] % 1000000000;
		LastNumberCounts[i][9] =	LastNumberCounts[i - 1][8] % 1000000000;

		for (int k = 1; k < 9; ++k)
			LastNumberCounts[i][k] = (LastNumberCounts[i-1][k-1] + LastNumberCounts[i-1][k + 1]) % 1000000000;
	}

	unsigned long long Res = 0;

	for (int i = 0; i <= 9; ++i)
		Res = (Res + LastNumberCounts[N][i]) % 1000000000;

	std::cout << Res << std::endl;


}