[10844] 쉬운 계단 수

문제

45656이란 수를 보자.

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

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

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

출력

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

입력 1

1

출력 1

9

입력 2

2

출력 2

17

1. 문제 설명

• 일단 1의 자리 숫자(1~9)는 뒤나 앞에 따라오는 숫자가 없으니 계단 수라고 가정한다.

• 예를 들어 n=2일 경우, dp[2][1]에는 10과 12가 해당되기 때문에 dp[2][1] = 2, dp[2][2] 일 경우 21, 23이 해당되기 때문에 dp[2][2] = 2.. 이런식으로 dp[2][9]까지 진행한다.
  n=3일 경우, dp[3][1]에는 101,121,123가 해당되고, dp[3][1] = 3, dp[3][2] 일 경우 212, 232, 234가 해당되기 때문에 dp[3][2] = 3.. 이런식으로 dp[3][9]까지 진행한다.

• 쉽게 말하자면 dp[이부분][]은 수의 길이(자릿수)를 의미하고 dp[][이부분]은 최상위 자릿수를 의미한다.
  dp[2][3]일 경우에 dp[3][] 는 3자리수(100~999)를 의미, dp[3][3] 은 숫자 3XX 를 의미한다. (XX는 dp[2][2]와 dp[2][4]를 넣어주면 된다. dp[2][2]를 붙이자면 321, 323이 된다.)

하.지.만.

• 그림에서 보다싶이 실제 값은dp[2][1] = 2가 아니고 dp[2][1] = 1 이다.
  왜 2가 아닐까? 싶겠지만 이걸 이해하여 구현한 사람이 대단하다는 생각이 든다.

1. 그림에서와 같이 n=2에서 [1]배열을 위에 설명한대로 대입하면 10, 12가 만들어진다. 총 2개지만, 하지만 0으로 시작할 수 없어 n=1일 때 [0] 부분에 개수를 0으로 설정했기 때문에 실제 n=1일 때 [2]의 1값만 들어왔다.
2. 하지만 n=2일 때 [0]배열을 보면 n=1일 때 [1]의 1값이 들어온 것이 보인다. 실제 위에 설명한대로 숫자를 만들면 01이 되는데, 문제에선 ‘0으로 시작하는 숫자는 세지 않는다’고 했다. 여기가 핵심이다.
   이건 거꾸로 보게되면 10이 된다.
3. 뒤쪽이 0으로 끝나는 숫자는 이런식으로 배열[0]에서 세도록 구현됐다.

• 마지막으로 그림을 보면 [0]과 [9] 는 앞,뒤로 가져올 배열이 없다. 그래서 해당 배열들은 각각 [1]과 [8]에서만 값을 가져올 수 있도록 구현해야 한다.

• [점화식]
  [0]일 때 : dp[i][0] = dp[i-1][1]
[9]일 때 : dp[i][9] = dp[i-1][1]
  그 외의 숫자일 때 : dp[i] = dp[i-1][j-1] + dp[i-1][j+1]
  문제에서 1,000,000,000로 나눈 나머지를 구하라고 하였으니,
  점화식 뒤에 % 1000000000를 적어주면 끝.

2. 소스 코드

#include <iostream>
#include <vector>

using namespace std;

const long long MOD = 1000000000;

int main() {
	int n;

	cin >> n;

	vector< vector<long long> > dp(n + 1, vector<long long>(11, 0));


	for (int i = 1; i < 10; i++) {
		dp[1][i] = 1;
	}

	for (int i = 2; i <= n; i++) {
		dp[i][0] = dp[i - 1][1] % MOD;
		dp[i][9] = dp[i - 1][8] % MOD;

		for (int j = 1; j <= 8; j++) {
			dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] % MOD;
		}
	}

	long long sum = 0;

	for (int i = 0; i < 10; i++) {
		sum += dp[n][i] % MOD;
	}

	cout << sum % MOD<< endl;

	return 0;
}