백준 BOJ 12849 본대 산책

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

12849번: 본대 산책

문제 해설

준영이가 정보과학관을 출발해 산책하고 정보과학관으로 돌아오는 데 D분이 걸린다.

=> D번의 건물 이동

 

정보과학관에 있던 준영이는 어디로 갈 수 있을까? 전산관, 미래관이다.

미래관으로 갔다면? 그로부터 1분 후에 위치할 수 있는 곳은? 정보과학관, 전산관, 신양관, 한경직기념관이다.

이처럼 위치한 곳에 따라 1분 후에 위치할 곳은 한정적이다.

 

경우의 수를 살펴보자

now_v[0]을 현재(T) 준영이가 정보과학관에 있는 경우의 수라고 해보자.

next_v[0]을 1분 후(T+1) 준영이가 정보과학관에 있는 경우의 수라고 해보자.

now_v[0]과 next_v[0]은 관련이 있을까? 없을 것 같다. 1분 후 이동해야 하니까!

 

now_v[1]을 현재(T) 준영이가 전산관에 있는 경우의 수라고 해보자.

now_v[1]과 next_v[0]은 연관이 있을까? 있을 것 같다. 1분 후 준영이가 이동할 수 있으니까!

같은 원리로 미래관도 연관이 있을 것이다.

현재 준영이가 위치한 장소들의 경우의 수를 토대로 1분 후 준영이가 위치한 장소들의 경우의 수를 구할 수 있다.

 

준영이는 정보과학관에서 출발하고, 정보과학관으로 돌아와야 한다. 이것만 추가하도록 하자.

 

#include <iostream>
#define fio cin.tie(0)->sync_with_stdio(0)
using namespace std;

long long Q = 1'000'000'007;
long long now_v[8];
long long next_v[8];
void time_goes(int time){
	for(int t = 0; t < time; t++){
		next_v[0] = now_v[1] + now_v[2]; next_v[0] %= Q;
		next_v[1] = now_v[0] + now_v[2] + now_v[3]; next_v[1] %= Q;
		next_v[2] = now_v[0] + now_v[1] + now_v[3] + now_v[4]; next_v[2] %= Q;
		next_v[3] = now_v[1] + now_v[2] + now_v[4] + now_v[5]; next_v[3] %= Q;
		next_v[4] = now_v[2] + now_v[3] + now_v[5] + now_v[6]; next_v[4] %= Q;
		next_v[5] = now_v[3] + now_v[4] + now_v[7]; next_v[5] %= Q;
		next_v[6] = now_v[4] + now_v[7]; next_v[6] %= Q;
		next_v[7] = now_v[5] + now_v[6]; next_v[7] %= Q;
		//
		for(int i=0; i<8; i++){
			now_v[i] = next_v[i];
		}
	}	
}
int main() {
	fio;
	int D; cin >> D;
	now_v[0] = 1;
	time_goes(D);
	cout << now_v[0];
	return 0;
}

 

비슷한 문제로 산책 시간(D)만 커진 문제 12850이 있다.

이 문제는 12849 코드로 제출 시 시간초과가 난다.

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

12850번: 본대 산책2