[210520][백준/BOJ] 10844번 쉬운 계단 수

문제

입출력

풀이

계단수란 인접한 모든 자리수의 차이가 1이 나는 수를 말한다.
45656는 모든 인접한 자리수가 1씩 차이가 난다. 따라서 이는 계단수이다.

n이 1일때는 1, 2, 3, 4, ... 9까지 총 개의 계단수가 있다. 문제에서 0으로 시작하는 수는 없다고 명시하였으므로 총 9개가 존재한다.

n이 2일때는 10, 12, 21, 23, ... 87, 89, 98까지 총 17개의 계단이 존재한다.

이러한 규칙을 이용해서 점화식을 만들어보면

d[n][L] = d[n-1][L-1] + d[n-1][L+1]
길이가 n, L은 숫자

임을 알 수 있다.

위 점화식은 L이 1부터 8까지 일때만 유효한 점화식이다.
0은 +1만 할 수 있으며 9는 -1만 할 수 있기 때문이다.
따라서 위 예외까지 합친 점화식은 다음과 같다

L이 0일때 d[n][L] = d[n-1][L+1]
L이 9일때 d[n][L] = d[n-1][L-1]
L이 1부터 8까지일때 d[n][L] = d[n-1][L-1] + d[n-1][L+1]

코드

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000000

int d[102][102];
int dp(int n)
{
	for (int i = 0; i < 9; ++i)
		d[1][i] = 1;

	for (int i = 2; i <= n; ++i)
	{
		for (int j = 0; j <= 9; ++j)
		{
			if (j == 0) d[i][j] = d[i - 1][j + 1] % MOD;
			else if (j == 9) d[i][j] = d[i - 1][j - 1] % MOD;
			else d[i][j] = (d[i - 1][j - 1] + d[i - 1][j + 1]) % MOD;
		}
	}
	int sum = 0;
	for (int i = 0; i < 10; ++i)
		sum = (sum + d[n][i]) % MOD;
	return sum;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	cout << dp(n);
}