[C++] 백준 12849번: 본대 산책

문제 링크

12849번: 본대 산책

문제 요약

8개의 정점으로 이루어진 그래프가 주어진다. 이 중 정보과학관에서 출발해서 d번 움직여서 다시 정보과학관으로 돌아올 수 있는 경로의 수를 구해야 한다.

접근 방법

크기가 8인 배열을 선언하고, 정보과학관만 1로 초기화 시켜줍니다. 현재 정점과 인접한 정점들의 현재 값의 합이 다음 이동시 해당 정점으로 가는 경우의 수가 됩니다. 따라서 이 절차를 d번 반복해주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

long long dp[8], nxt[8];

int main(void)
{
	int d;
	cin >> d;

	dp[0] = 1;
	while (d--)
	{
		nxt[0] = dp[1] + dp[2];
		nxt[1] = dp[0] + dp[2] + dp[3];
		nxt[2] = dp[0] + dp[1] + dp[3] + dp[4];
		nxt[3] = dp[1] + dp[2] + dp[4] + dp[5];
		nxt[4] = dp[2] + dp[3] + dp[5] + dp[6];
		nxt[5] = dp[3] + dp[4] + dp[7];
		nxt[6] = dp[4] + dp[7];
		nxt[7] = dp[5] + dp[6];

		for (int i = 0; i < 8; i++)
			dp[i] = nxt[i] % 1000000007;
	}

	cout << dp[0];
	return 0;
}