[C++] BOJ / 10844번 / 쉬운 계단 수

10844번: 쉬운 계단 수

 

- 문제

45656이란 수를 보자.

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

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

 

- 입력

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

2

 

- 출력

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

17

---

#include <iostream>

using namespace std;

#define MOD 1000000000

long long DP[101][10];

int main()
{
	int n, ans = 0;

	cin >> n;

	DP[1][0] = 0;
	for (int i = 1; i <= 9; ++i)
		DP[1][i] = 1;

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

	for (int i = 0; i < 10; ++i)
		ans = (ans + DP[n][i]) % MOD;
	cout << ans;
}

---

결과분석

계단의 길이가 i 일 때, 계단 수의 개수는 계단의 길이가 i - 1 일 때의 계단 수 뒤에 차이가 1인 숫자 하나를 추가하는 것과 같다. 예를 들어, 계단 수가 1로 끝났을 경우 뒤에 추가될 수 있는 숫자는 0 또는 2이다. 때문에 다음과 같은 점화식을 도출해낼 수 있다.

 

DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j + 1]

 

다만 j가 0 또는 9일 경우, 즉 계단 수가 0 으로 끝났을 경우에는 +1만 가능하며, 계단 수가 9로 끝났을 경우에는 -1만 가능하기 때문에 따로 처리해주어야 한다.