(백준/C++) 10844_쉬운 계단 수

10844번: 쉬운 계단 수 문제는 동적 계획법으로 풀 수 있는 문제입니다.

동적 계획법(Dynamic Programming, DP)은 큰 문제를 작은 문제들로 나누어 풀어나가고 작은 문제의 해를 저장해 다시 계산하지 않고 사용하는 방식입니다.

동적 계획법 문제는 최적 부분 구조와 중복된 부분 문제의 두 가지 속성을 가진 문제에 유용합니다.

쉬운 계단 수 문제가 왜 이러한 동적 계획법을 적용할 수 있는지 확인해보겠습니다.

1. 최적 부분 구조: N자리 계단 수를 구하기 위해 N-1자리 계단 수의 해결책을 활용합니다.
   예를 들어 3자리 계단 수 “121”을 만들기 위해서는 2자리 계단 수 “12”의 해결책 다음에 숫자 “1”을 더하는 방식으로 만들 수 있습니다.
2. 중복된 부분 문제: 동일한 작은 문제가 반복적으로 발생합니다.
   특정 자리수에서의 계단 수를 계산할 때 이전 자리수의 계단 수를 반복해서 참조해야 하기 때문입니다.

---

접근법

우선, 계단 수의 특성을 고려하면 각 자리수와 인접한 숫자에 대한 점화식을 짜야 한다는 것을 생각할 수 있습니다.

길이가 1이면서 마지막 숫자가 1인 경우의 수, 길이가 2이면서 마지막 숫자가 1과 인접한 어떤 수, ⋯.

하지만, 이렇게 생각해봐도 처음 이 문제를 접했을 때, 점화식이 쉽게 생각나지 않습니다.

따라서 먼저 표로 접근해 보겠습니다.

1. Tabulation (Bottom-up)식 생각하기

우선, 각 자리수에 대해 어떤 숫자가 올 수 있는지 생각해 봅시다.

위와 같이 “특정 숫자로 끝나는 경우” 그 앞에 올 수 있는 숫자는 해당 숫자 +1 또는 -1 두 가지입니다.

이에 따라 각 경우의 수를 표로 만들어보면, 다음과 같이 표현될 수 있습니다.

2. 점화식 만들기

위의 표를 보면, “길이가 i이고 j로 끝나는 계단 수”는 “이전 길이(i-1)의 j-1 또는 j+1로 끝나는 계단 수”의 합임을 알 수 있습니다.

즉, 길이가 2이고 3으로 끝나는 계단 수의 경우는 길이가 1이고 2로 끝나는 계단 수와 길이가 1이고 4로 끝나는 계단 수의 합과 같습니다.

---

풀이

이 문제는 점화식을 생각해 내는데 시간이 오래 걸린 문제입니다. 처음부터 2차원 배열로 만들 생각을 못했던 거였죠.

하지만, 2차원 배열로 만들어내고 점화식을 도출했다면 푸는 것은 생각보다 쉬웠습니다.

점화식은 다음과 같습니다.

S[i][j] = (S[i-1][j-1] + S[i-1][j+1]) 이전 길이의 1 작은 수와 1 큰 수의 경우의 수를 합하면 됩니다. (이때, 0과 9로 끝나는 수는 앞에 수가 1개 밖에 오지 않으니 예외 처리를 해줘야 합니다.)

#include <iostream>
using namespace std;
constexpr int MOD = 1e9;
int stairs[101][10];
void stairNumCnt(int N)
{
	//길이가 1인 경우 초기화
	for(int i = 1; i <= 9; i++)
		stairs[1][i] = 1;

	//길이가 2 부터 N 까지 초기화
	for(int i = 2; i <= N; i++)
	{
		for(int j = 0; j <= 9; j++)
		{
			if (j == 0) 
				stairs[i][j] = stairs[i - 1][1] % MOD; //끝이 0으로 끝나는 경우 1밖에 못온다.
			else if (j == 9) 
				stairs[i][j] = stairs[i - 1][8] % MOD; //역시 끝이 9로 끝나는 경우 8밖에 못온다.
			else
				stairs[i][j] = (stairs[i - 1][j - 1] + stairs[i - 1][j + 1]) % MOD;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;

	stairNumCnt(N);

	int sum = 0;
	for (int i = 0; i <= 9; i++)
		sum = (sum + stairs[N][i]) % MOD;

	cout << sum;
}