백준 10844번: 쉬운 계단 수

[문제 링크]

10844번: 쉬운 계단 수

---

5개월 전에 책 없이 공부할 때 결국 못풀고 포기한 문제였다. 그 당시엔 정말 어렵게 느껴졌던 문제였는데 동적계획법을 제대로 이해하고 보니 풀이법을 금방 생각해낼 수 있었다.

 

 0~9 사이의 숫자 number로 시작하는 길이가 N인 계단수는 number-1로 시작하는 길이가 N-1인 계단수 + number+1로 시작하는 길이가 N-1인 계단수와 같다. 그리고 number가 0일 때 number-1인 -1과 9일 때 number+1인 10은 0~9 사이의 숫자가 아니므로 계산에서 제외시켜야 한다.

따라서 이 문제의 점화식을 다음과 같이 표현할 수 있다.

 

if (number == 0)  dp(N, number) = dp(N-1, number+1)

else if (number == 9)  dp(N, number) = dp(N-1, number-1)

else  dp(N, number) = dp(N-1, number-1) + dp(N-1, number+1)

 

위 점화식을 알고리즘으로 구현하면 원하는 결과를 얻을 수 있다.

---

#include <iostream>
using namespace std;

const int MOD = 1000000000;
int memo[101][10];

int TopDown(int n, int here)
{
	if (n == 1) return 1;

	int& ret = memo[n][here];
	if (ret != 0) return ret;

	if (here == 0)
		return ret = TopDown(n - 1, here + 1) % MOD;
	else if (here == 9)
		return ret = TopDown(n - 1, here - 1) % MOD;
	else
		return ret = (TopDown(n - 1, here - 1) + TopDown(n - 1, here + 1)) % MOD;
}

int BottomUp(int n)
{
	for (int i = 0; i <= 9; i++)
		memo[1][i] = 1;

	for (int i = 2; i <= n; i++)
	{
		for (int j = 0; j <= 9; j++)
		{
			if (j == 0)
				memo[i][j] = memo[i - 1][j + 1] % MOD;
			else if (j == 9)
				memo[i][j] = memo[i - 1][j - 1] % MOD;
			else
				memo[i][j] = (memo[i - 1][j - 1] + memo[i - 1][j + 1]) % MOD;
		}
	}
	int res = 0;
	for (int i = 1; i <= 9; i++)
	{
		res += memo[n][i];
		res %= MOD;	// memo[n][i]가 3,000,000,00 정도의 값이라고 생각했을 때
        			// 1~9까지 반복하여 더하다보면 10억을 넘어갈 수 있기 때문에 %=MOD 해줌
	}

	return res;
}
int main(void)
{
	int n;
	cin >> n;
	
	// Top-Down
	int res = 0;
	for (int i = 1; i <= 9; i++)
	{
		res += TopDown(n, i);
		res %= MOD; // 위와 동일
	}
	cout << res << endl;

	// Bottom-Up
	cout << BottomUp(n) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 65 day