쉬운 계단 수 (백준 - 10844번)

동적 계획법을 이용하여 해결하는 문제였다.

 

점화식을 찾기 위해 1부터 차례대로 구해보자.

 

N = 1일 때는 1부터 9까지 모두 계단 수이다.

(0은 계단 수가 아니라는 것을 명시했기 때문에 제외해야 한다)

=> 1, 2, 3, 4, 5, 6, ...., 9 이므로 

 

N = 2일 때에는 계단 수는 다음과 같다.

=> 10, 21, 12, 32, 23, 43, 34, ...., 89

 

N = 2일 경우 계단 수에서 마지막 수를 잘 살펴보면 0 ~ 9까지 차례대로 나온다는 것을 알수 있고, 그 앞자리에는 +-1이 온다는 것을 알 수 있다. 

 

N = 2에서 마지막 수가 3일 경우 

X3 (X에는 2와 4가 오기 때문에 N = 1에서 2와 4가 오면 된다.)

그러므로 23, 43이 계단수로 온다.

 

N = 3에서 마지막 수가 3일 경우

XY3 (Y에는 2와 4가 오고 Y가 2일때 X는 1과 3, Y가 4일때 X는 3과 4가 온다.)

그러므로 이전 N = 2에서 마지막 수가 2일때의 12와 32 그리고 마지막 수가 4일때의 34와 54가 XY에 오기 때문에 123, 323, 343, 543이 계단수로 나온다.

 

그러므로 점화식은 다음과 같다.

 

길이가 N이고 마지막수 L이고, DP 테이블 배열 DP[N][L]이 있다고 가정했을떄,

DP[N][L] = DP[N-1][L-1] + DP[N-1][L+1]이다. 

 

하지만 주의할 점이 있는데 위의 점화식은 L이 1~8 일때만 성립한다.

왜냐하면 0은 -1의 값이 없으므로 +1을 한 1만 허용되고 9 또한 +1 값이 없으므로 -1을 한 8만 적용되기 때문이다.

 

이를 적용하여 최종적인 점화식은 다음과 같다.

 

L = 0 일때

=> DP[N][L] = DP[N-1][L+1]

 

L = 1 ~ 8 일때

=> DP[N][L] = DP[N-1][L-1] + DP[N-1][L+1]

 

L = 9 일때

=> DP[N][L] = DP[N-1][L-1]

 

결과값을 1,000,000,000과 나눈 나머지를 출력해야 하기 때문에 DP값은 구한 계단수 갯수에 1,000,000,000을 나눈 나머지 값이 와야 한다. 그리고 N번째의 L이 0부터 9까지의 계단수를 더한 값이 최종 결과값이 되므로 DP[N][0] ~ DP[N][9]를 모두 더해주면 된다.

 

코드는 다음과 같다.

#include <iostream>
using namespace std;
const int mod = 1000000000;

int main()
{
	long long DP[101][10] = { 0, };
	
	int input;
	cin >> input;

	for (int i = 1; i <= 9; ++i)
	{
		DP[1][i] = 1;
	}
	
	for (int i = 2; i <= input; ++i)
	{
		for (int j = 0; j <= 9; ++j)
		{
			if (0 == j)
				DP[i][j] = DP[i - 1][j + 1] % mod;
			else if (9 == j)
				DP[i][j] = DP[i - 1][j - 1] % mod;
			else
				DP[i][j] = DP[i - 1][j + 1] + DP[i - 1][j - 1] % mod;
		}
	}

	long long sum = 0;
	for (int i = 0; i <= 9; ++i)
	{
		sum += DP[input][i];
	}

	cout << sum % mod << endl;
}