백준 10844 - 쉬운 계단 수

문제 번호: 10844

문제 제목: 쉬운 계단 수

문제 주소: https://www.acmicpc.net/problem/10844

문제 내용

글자 수 N이 주어졌을 때 N글자로 만들 수 있는 계단 수의 가짓수를 10억으로 나눈 나머지로 출력한다.
계단수는 45656처럼 인접한 숫자 간의 차의 절대값이 1인 수를 의미한다. 단, 0으로 시작할 수는 없다.

테스트 케이스

1	9
2	17
100	18404112

문제 풀이

i으로 끝나는 숫자는 그 다음 숫자가 i - 1, i + 1이 된다.
즉, N - 1글자의 M으로 끝나는 수는 N글자의 M - 1인 수와 M + 1인 수가 된다.
이를 표로 나타내보면 아래와 같다.

N	0	1	2	3	4	5	6	7	8	9
1	0	1	1	1	1	1	1	1	1	1
2	1	1	2	2	2	2	2	2	2	1
3	1	3	3	4	4	4	4	4	3	2
4	3	4	7	7	8	8	8	7	6	3
5	4	10	11	15	15	16	15	14	10	6

따라서 동적계획법으로 코드를 작성한다면 위와 같이 N*10개짜리 배열을 만들고 1~8는 N-1의 i - 1과 i + 1를 합친 값을 대입하고, 0은 N-1의 1 값을, 9는 N-1의 8 값을 대입하는 것으로 N자의 글자 수를 구할 수 있다.

풀이 코드

#include <iostream>
using namespace std;

void BAEKJOON_10844()
{
	const uint32_t MOD = 1000000000;
	int N;
	cin >> N;
	uint32_t result = 0;
	if (N == 1)
	{
		result = 9;
	}
	else
	{
		uint32_t numArr[101][10] = { 0 };
		/*---------------1열 초기화------------------*/
		numArr[1][0] = 0;
		for (int pos = 1; pos <= 9; pos++)
		{
			numArr[1][pos] = 1;
		}
		/*---------------N열 계산--------------------*/
		for (int culumn = 2; culumn <= N; culumn++)
		{
			for (int pos = 0; pos <= 9; pos++)
			{
				if (pos > 0)
				{
					numArr[culumn][pos] += numArr[culumn - 1][pos - 1];
				}
				if (pos < 9)
				{
					numArr[culumn][pos] += numArr[culumn - 1][pos + 1];
				}
				numArr[culumn][pos] %= MOD;
			}
		}
		/*---------------result 구하기---------------*/
		for (int pos = 0; pos <= 9; pos++)
		{
			result += numArr[N][pos];
			result %= MOD;
		}
	}
	cout << result << endl;
	return;
}