[BOJ 10844] 쉬운 계단 수

 

10844번: 쉬운 계단 수

인접한 수가 1이 차이나도록 하는 수를 계단수라고 정의합니다.

123 = 계단수, 121 = 계단수, 124 != 계단수, 125 != 계단수

 

1. N : 최대 100자리의 수

 

DP배열을 정의합니다.

 - DP[i][j] : i자리수 중 j로 끝나는 수의 개수

i / j	0	1	2	3	4	5	6	7	8	9
1	0	1	1	1	1	1	1	1	1	1
2	1	1	2	2	2	2	2	2	2	1
3	1	3	3	4	4	4	4	4	3	2
4	3	4	7	8	8	8	8	7	6	3
5	4	10	12	15	16	16	15	14	10	6
6	10	16	25	28	31	31	30	25	20	10
7	16	35	44	56	59	61	56	50	35	20
8	35	60	91	103	117	115	111	91	70	35
9	60	126	163	208	218	228	206	181	126	70

 

* 자리수가 i라고 했을 때, j로 끝나는 자리수의 개수 DP[i][j] : DP[i-1][j-1] + DP[i-1][j+1]

   - 0으로 끝나는 자리수의 경우 : 이전의 자리수가 1로 끝나는 자리수의 개수 (0은 무조건 1에서만 갈 수 있음)

   - 9로 끝나는 자리수의 경우 : 이전의 자리수가 8로 끝나는 자리수의 개수  ( 9는 무조건 8에서만 갈 수 있음)

 

DP[7][0] = DP[6][1]

DP[7][9] = DP[6][8]

DP[3][2] = DP[2][1] + DP[2][3]

DP[4][4] = DP[3][3] + DP[3][5]

 

자리수가 1인 수의 개수를 알면 자리수가 2인 수의 개수를 알고, 2인 수의 개수를 알면 3의 수의 개수를 알고..

main Problem : n의 자리수를 구하기 위해 n보다 작은 자리수들의 개수를 이용해 문제를 풀이하기 때문에

위의 점화식을 기반으로 동적계힉법으로 풀이하는 문제입니다.

해당 문제에서 1,000,000,000으로 나눈 수를 출력하라 하였기 때문에 연산마다 %연산을 해주어 답 출력!

 

#include <iostream>

#define mod 1000000000

using namespace std;

long long dp[101][10] = { 0, };

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int n;
	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 <= 8; j++)
		{
			dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
		}
	}

	long long res = 0;
	for (int i = 0; i <= 9; i++)
	{
		res = (res + dp[n][i]) % mod;
	}

	cout << res;

}