[백준/BOJ] 백준 12849번 : 본대 산책

www.acmicpc.net/problem/12849

12849번: 본대 산책

그래프를 만들고, 현재 위치와 지난 시간을 고려하여 long long cache[8][100001]를 사용해 중복계산을 하지 않는다.

 

코드

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

int d;
vector<int> adj[8]; //정보과학관, 전산관, 신양관, 진리관, 학생회관, 형남공학관, 한경직기념관, 미래관 순서(0~7)
long long cache[8][100001];

//그래프를 만들고 cache를 초기화한다
void Pre()
{
	for (int i = 0; i < 8; i++)
	{
		int left = i - 1;
		int right = i + 1;

		if (left < 0)
			left = 7;
		if (right > 7)
			right = 0;

		adj[i].push_back(left);
		adj[i].push_back(right);
	}

	adj[1].push_back(7);
	adj[2].push_back(6);
	adj[2].push_back(7);
	adj[3].push_back(6);
	adj[6].push_back(2);
	adj[6].push_back(3);
	adj[7].push_back(1);
	adj[7].push_back(2);

	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 100001; j++)
			cache[i][j] = -1;
}

//here:현재위치, cnt:지난 시간
int Solve(int here, int cnt)
{
	if (cnt == d)
	{
		if (here == 0) //정보 과학관일때
			return 1;
		else
			return 0;
	}

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

	if (ret != -1)
		return ret;

	ret = 0;

	for (int i = 0; i < adj[here].size(); i++)
	{
		int there = adj[here][i];

		ret += (Solve(there, cnt + 1) + 1000000007) % 1000000007;
	}

	ret %= 1000000007;

	return ret;
}

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

	cin >> d;

	Pre();

	cout << Solve(0, 0);

	return 0;
}