[C++] 10844: 쉬운 계단 수

문제

45656이란 수를 보자.

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

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

입력

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

출력

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

예제 입력 1

1

예제 출력 1

9

풀이

먼저 dp니까 2차원 배열을 사용할 것 같아서 이리저리 생각해보았다. 계단수를 만드려면 2차원 배열에서 그릴 수 있는 모든 대각선(지그재그 포함)을 구하면 된다! 예를 들어서 n == 3일 때, 100의 자리가 2로 시작하는 계단수는 다음과 같다.
210, 212, 232, 234 총 4개이다.
따라서 1의 자리를 모두 1로 두고, 왼쪽으로 가면서 오른쪽 대각선 위와 아래를 더하여 저장하면, 해당 좌표에서 오른쪽으로 그릴 수 있는 대각선(지그재그)의 총 수가 저장된다!

n의 자리가 0이면 안 되므로, 0만 빼고 마지막에 [1][0]부터 [9][0]까지 모두 더해주고 1,000,000,000으로 나누면 정답이 나온다!

주의할 점이 있는데, n이 무척 커지면 2차원 배열 내에 저장되는 숫자도 너무너무 커진다. 따라서 저장할 때마다 1,000,000,000으로 나눠주면 된다. 계산마다 나눈다 하더라도, 어차피 1,000,000,000보다 작은 자릿수들은 나누나 안 나누나 똑같기 때문에 상관 없다. 마지막에 정답을 계산할 때도 더할 때마다 1,000,000,000으로 나눠주면 된다.

코드

#include <iostream>

using namespace std;

int n;
int dp[10][100];
int move_x[2] = {1, 1};
int move_y[2] = {1, -1};

void input_data(void);
void stair(void);

int main(void)
{
	input_data();
	stair();

	return (0);
}

void input_data(void)
{
	cin >> n;
	
	int i = -1;
	while (++i < 10)
		dp[i][n - 1] = 1;

	return ;
}

void stair(void)
{
	int x = n - 1;
	
	while (--x >= 0)
	{
		int y = -1;
		while (++y < 10)
		{
			int move = -1;
			while (++move < 2)
			{
				int next_x = x + move_x[move];
				int next_y = y + move_y[move];

				if (next_y >= 0 && next_y < 10)
					dp[y][x] += dp[next_y][next_x];
			}
			dp[y][x] %= 1000000000;
		}
	}

	int i = 0;
	int count = 0;
	while (++i < 10)
	{
		count += dp[i][0];
		count %= 1000000000;
	}
	cout << count << '\n';

	return ;

}

딩동댕 정답~!