[백준/BOJ] 백준 1562번 : 계단 수

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

1562번: 계단 수

int cache[10][100][1 << 10];에 [현재 숫자][현재 숫자의 인덱스][이전에 어떤 숫자가 쓰였는지 비트로 표현]일 때의 계단수의 개수를 저장하여 다이나믹 프로그래밍을 이용해서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
int result = 0;
int cache[10][100][1 << 10];

void Pre()
{
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 100; j++)
			for (int k = 0; k < (1 << 10); k++)
				cache[i][j][k] = -1;
}

//here_number:현재 숫자. index:위치, check:어떤숫자가 쓰였는지 비트로 표현
int Solve(int here_number, int index, int check)
{
	//모든 위치를 다 확인 했을때
	if (index == n - 1)
	{
		//모든 숫자가 다 쓰였는지 확인
		if (check == ((1 << 10) - 1))
			return 1;

		else
			return 0;
	}

	int& ret = cache[here_number][index][check];

	if (ret != -1)
		return ret;

	ret = 0;

	if (here_number - 1 >= 0)
		ret = (ret + Solve(here_number - 1, index + 1, check | (1 << (here_number - 1)))) % 1000000000;

	if (here_number + 1 <= 9)
		ret = (ret + Solve(here_number + 1, index + 1, check | (1 << (here_number + 1)))) % 1000000000;

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	Pre();
	for (int i = 0; i <= 9; i++)
	{
		if (i == 0)
			continue;

		int here_number = i;
		int index = 0;
		int check = 0;

		check |= (1 << i);
		result = (result + Solve(here_number, index, check)) % 1000000000;
	}

	cout << result;

	return 0;
}