백준 10844 번 - 쉬운계단수 (C++/DP/동적계획법/Dynamic Programming)

문제

45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

접근법

동적계획법으로 접근해야 하는 문제이다.

여러가지 예시를 보며 문제부터 파악했다.

 

자리수를 Y, 맨 뒤 index에 따른 개수를 X로 두고, 2차원 배열을 만들면

cnt[101][10]; 정도로 크기를 두며 이전 값을 참고해 채워나가면 될거같다.

 

자리수는 2인 것

끝자리 0 -> 10

끝자리 1-> 21

끝자리 2->32,12

끝자리 3->23,43

끝자리 4->34,54

.

.

.

끝자리 8->78,98

끝자리 9->89

맨 앞자리는 0이 올수 없으므로 위 17가지가 계단수이다.

 

자리수가 3인것

끝자리 0 -> 210 (맨 뒤 0을 때고보면 21) -> 자리수가 1인것의 끝자리 1인것(예외케이스)

끝자리 1 -> 321,101,121 -> 맨 뒤 (1을 때고보면 32,10,12) -> 자리수가 2인것에서 끝자리 0,2 조합 

끝자리 2 -> 432,232,212 (맨 뒤 2를 때고보면 43,23,21) -> 자리수가 2인것에서 끝자리 1,3 조합

끝자리 3 -> 123,543,323,343 (맨 뒤 3을 때고보면 12,54,32,34) -> 자리수가 2인것에서 끝자리 2,4 조합

.

.

.

끝자리 9 -> 989,789(맨뒤 9를 때고보면 98,78) -> 자리수가 2인것에서 끝자리 8인것 (예외케이스)

 

즉 위 2가지 예외케이스를 제외하고 점화식을 써보면

 

if (j == 0)

    cnt[i][0] = cnt[i - 1][1] % MOD;

else if (j == 9)

    cnt[i][9] = cnt[i - 1][8] % MOD;

else

    cnt[i][j] = (cnt[i - 1][j - 1] + cnt[i - 1][j + 1]) % MOD;

(MOD는 1000000000, 문제 조건)

 

 

 

코드

/*
45656이란 수를 보자.

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

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

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

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

#include <iostream>
using namespace std;

#define MOD 1000000000

long long cnt[101][10] = { 0, }; // 101자리수 중 

long long stairNums(long long N)
{
	long long nums = 0;

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

	for (int i = 2; i <= N; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			if (j == 0)
				cnt[i][0] = cnt[i - 1][1] % MOD;
			else if (j == 9)
				cnt[i][9] = cnt[i - 1][8] % MOD;
			else
				cnt[i][j] = (cnt[i - 1][j - 1] + cnt[i - 1][j + 1]) % MOD;
		}
	}
	for (int i = 0; i < 10; i++)
	{
		nums += cnt[N][i] % MOD;
	}
	return nums % MOD;
}

int main()
{
	long long N;
	cin >> N;
	cout << stairNums(N);
}