[백준/BOJ] 백준 22236번 : 가희와 비행기

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

22236번: 가희와 비행기

cache에 해당 위치, 해당 높이에서의 결과를 저장해서, 다이나믹 프로그래밍을 통해 문제를 해결했다

 

코드

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

long long cache[4005][4005]; //[위치][높이] = 도착점에 이륙하는 경우의 수
long long d, m;
int start;
int dest;

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

long long Solve(int here, int height)
{
	//도착지점에 도착 했을때
	if (here == dest)
	{
		if (height == 0)
			return 1;
		else
			return 0;
	}

	//도착지점, 출발지점이 아닌데 이륙되었을때
	if (height == 0 && here != start)
		return 0;

	if (height < 0)
		return 0;

	long long& ret = cache[here][height];

	if (ret != -1)
		return ret;

	int up_height = height + 1;
	int down_height = height - 1;

	ret = (Solve(here + 1, up_height) + Solve(here + 1, down_height)) % m;

	return ret;
}

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

	Pre();

	cin >> d >> m;

	start = 0;
	dest = d;

	cout << Solve(0, 0);

	return 0;
}