[백준/C++] 12849 본대 산책

사실 엄청 도움되는 글은 아닙니다. 정리가 잘 되어있지도 않고, 거의 직관적으로 문제를 해결해서 제 답이 옳은지 틀린지도 잘 모릅니다.. 아무쪼록 걸러 읽으시길 바라겠습니다..

저번 글에서 DP를 안해서 하기 싫다고, 내 지식이 탄로나기 싫다고! 이런식으로 적지 않았지만

실제로 이러한 기분이였습니다. 그래도 지식을 채우려면 항상 내가 싫어하는 것을 먼저 해야된다고 생각을 합니다. 그래야 발전도 있고 지루한 일상에서 쾌감도 얻고 뿌듯함도 가져가는 것 아닐까요?

말이 길었네요 실버 1 문제지만 이렇게 좀 의미부여를 해야 확실히 문제를 풀 맛이 나겠죠?

해당 문제는 본대 산책이라는 문제인데, 예전에 문제를 보고나서 이게 뭐야 하고 넘어갔던 적이 있습니다. 그래서 오늘은 풀이를 해보자 생각을 해서 무작정 문제에 달려들었습니다.

일단 고정된 그래프가 하나 주어지고, 이 문제의 목적은 정보과학관에서 출발해 D분안에 다시 돌아오는 즉 D분에 정보과학관으로 다시 돌아오는 산책길이 몇개인지 파악을 하라는 문제입니다.

보통 DP문제를 풀때 저는 예제를 먼저 보고 힌트를 얻습니다. 일단 D = 10 출력은 9857 뭔가 숫자가 이상하죠? 저도 보고나서 좀 어이가 없었습니다. 이거 어떻게 풀지?

곰곰히 생각을 해봤습니다. 일단 가장 중요한 힌트 하나는 그래프가 고정이라는 점, 그렇다면 길은 늘어나는 것이 아닌 고정적이고 어떠한 방법이 있을것이라는점?

그렇게 생각해 A4용지에 끄적이면서 문제를 풀 실마리를 찾고 있었습니다. 흠... 계속해서 왔다갔다하는 것도 하나의 경우의 수이기 때문에 중복은 당연히 가능하고... 어떻게 해결을 해볼까?

하면서 10이라는 숫자에 매몰되어있었습니다. 하지만, DP란 자고로 작은 문제부터 천천히 해결해나가면 문제가 또 풀리지 않겠습니까? D = 1 이라는 값을 먼저 생각해서 문제를 해결해 보아야겠습니다.

D=1 이라면? 정보과학관에 있어야겠죠? 1이니까 1에는 정보과학관에 있어야하니까? 그리고 2라면? 전산관 그리고 미래관에 도달할 수 있겠구나? 근데 전산관 미래관 정보과학관에 갈수 있는 길의 경우의 수를 다 세어주어야 하니까 그 값을 전부 다 더하면 되지 않을까?라는 생각이 번뜩였습니다.

와 난 천재다 생각하면서 시계를 봤더니 하루가 지나있었습니다. 진짜 이 시간까지 걸리진 않았지만 어쨌든 좀 생각하는데 시간을 좀 쏟았습니다. 그렇게 식을 생각해본 결과 해당 코드가 완성이 되었습니다.

 

매 초마다 이동할 수 있는 곳을 업데이트 해가며 모든 길을 체크해야합니다. 처음엔

[1,0,0,0,0,0,0] 이런식으로 배열이 나와있겠죠? D = 1이 지나고, 2.. 3.. 4.. 이런식으로 지나다보면? 해당 과학관까지의 경우의수가 다 저장되어 있을 것입니다. 정답을 맞춘 후 다른 사람들의 풀이도 파악해본 결과 비슷한 풀이가 많은것을 봐선 그래도 정해에 가까운가 봅니다.

#include <iostream>

using namespace std;

long long dp[8], n[8];

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

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

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

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