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

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

index(0이면 시작, 첫 번째 원소는 1) 번째 원소가 index_num일 때(index가 0(시작)일 때는 의미 없다) 계단수의 개수를 구하는 함수를 만든다. 주의해야 할 점은 index가 0이면 시작을 index가 0이면(처음시작) 첫 번째 수가 1~9인 것을 모두 확인하므로 이때 index_num는 의미 없고, 이렇게 모든 계단 수를 구할  수 있다. 또한 주의해야 할 점은 값에 % 1000000000을 하는 건데 solve함수의 마지막 리턴값에만 하는 것이 아니라, (solve(index + 1, index_num - 1) + solve(index + 1, index_num + 1)) % 1000000000; 와 값이 오버플로우가 일어날 수 있는 곳에도 해주어야 한다.

 

코드

#include <iostream>
#include <cstring>
using namespace std;

int n;
long long cache[101][10];

//index(0이면 시작, 첫번째 원소는 1)번째 원소가 index_num일때(index가 0(시작)일때는 의미 없다) 계단수의 개수를 구한다
long long solve(int index, int index_num)
{
	//어떤 계단수의 마지막일때
	if (index == n)
		return 1;

	long long& ret = cache[index][index_num];

	//이미 계산된적 있는 값일때
	if (ret != -1)
		return ret;

	ret = 0;

	//index가 0이면(처음시작) 첫번째수가 1~9인 길이 n짜리 계단수를 모두 구한다
	//index가 0이면(처음시작) 첫번째수가 1~9인것을 모두 확인하므로 이때 index_num는 의미 없다
	if (index == 0)
	{
		for (int i = 1; i <= 9; i++)
		{
			ret += solve(index + 1, i);
		}
	}

	else
	{
		if (index_num == 0) //index_num이 0이면 다음 원소는 무조건 1 뿐이다
			ret += solve(index + 1, 1);

		else if (index_num == 9) //index_num이 9면 다음 원소는 무조건 8 뿐이다
			ret += solve(index + 1, 8);

		else //다음 원소가 index_num-1인 경우와 index_num+1인 경우를 모두 구한다
			ret += (solve(index + 1, index_num - 1) + solve(index + 1, index_num + 1)) % 1000000000;
	}

	return ret % 1000000000;
}
int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	memset(cache, -1, sizeof(cache));

	long long result;

	cin >> n;

	//int solve(int index, int index_num)에서
	//index가 0이면 시작을 나타내고 이떄 index_num은 의미 없다 (이때 int cache[101][10] 이므로 index_num을 0~9 아무수 나 넣어두자)
	result = solve(0, 0);

	cout << result;

	return 0;
}