백준 10844번, 쉬운 계단 수

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1 

1

예제 출력 1

9

예제 입력 2 

2

예제 출력 2 

17

 

 조건이 있는 다이나믹 프로그래밍 문제이다. 기본적인 골자는 k 자리수의 모든 수에 대해서 계단수를 만족하는 경우의 수를 그 이전에 구해놓은 k-1 자리 수의 모든 경우의 수로 부터 연쇄적으로 이끌어내는 것이다. 문제 조건을 충족하는 지 판단히기 위해서 모든 경우의 수를 하나로 합쳐서 저장하지 않고, k 자리 수 + 마지막 수가 0 으로 끝나는 경우, k 자리 수 + 마지막 수가 1 로 끝나는 경우, ... , k 자리 수 + 마지막 수가 9 로 끝나는 경우로 나누어 저장하였다. 나누어 저장하는 것이 이 문제를 해결하기 위한 가장 중요한 포인트이다.

 나는 다음과 같이 문제를 해결하였다.

 

1. 자릿수 N을 입력으로 받는다.
2. 이중배열 cases[101][10]을 선언한다. (N의 최대값이 100 이므로...)
3. N = 1인 경우에 대해 cases[1][0] ~ cases[1][9]를 채워 놓는다.
4. N = 2 인 경우부터 입력값까지 연쇄적으로 배열을 채워 놓는다. 이 때 cases[k][0] = cases[k-1][1], cases[k][9] = cases[k-1][8], cases[k][j] = cases[k][j-1] + cases[k][j+1] (j = 1, 2, ..., 8) 이다. 값이 커질 경우를 위해 미리 모듈러 연산을 취해 주었다.
5. 입력값에 대해서 (cases[N][0] + ... + cases[N][9]) 를 모듈러 연산을 취한 후 이를 출력한다.   

 

 코드는 다음과 같다.

 

#include <iostream>
#include <deque>

#define MOD 1000000000

int cases[101][10];

int main() 
{
	int N;
	std::cin >> N;

	cases[1][0] = 0;
	cases[1][1] = 1;
	cases[1][2] = 1;
	cases[1][3] = 1;
	cases[1][4] = 1;
	cases[1][5] = 1;
	cases[1][6] = 1;
	cases[1][7] = 1;
	cases[1][8] = 1;
	cases[1][9] = 1;

	if (N > 1) 
	{
		for (int i = 2; i <= N; i++)
		{
			cases[i][0] = cases[i - 1][1];
			
			for (int j = 1; j <= 8; j++) 
			{
				cases[i][j] = (cases[i - 1][j - 1] + cases[i-1][j + 1]) % MOD;
			}

			cases[i][9] = cases[i - 1][8];
		}
	}

	long long out = 0;

	for (int i = 0; i < 10; i++) 
	{
		out += cases[N][i];
	}

	std::cout << out % MOD;

	return 0;
}

 

 조건이 있는 다이나믹 프로그래밍 문제는 조건을 판단하기 위해 각 경우에 대해서도 값을 저장해 놓아야 한다는 것을 상기 시켜주는 문제였다. 이 것으로 글을 마친다.