백준 BOJ 12850 본대 산책2

 

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

12850번: 본대 산책2

12849 본대 산책 문제와 거의 같다.

산책 시간(D)이 매우 커졌을 뿐.

 

문제 해설

준영이가 정보과학관을 출발해 산책하고 정보과학관으로 돌아오는 데 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분 후 준영이가 위치한 장소들의 경우의 수를 구할 수 있다.

 

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

 

---------------------- 여기까지 12849와 같다. --------------------

 

그런데 산책을 너무 오래한다. 경우의 수도, 계산량도 너무 커진다.

계산량을 줄여야 한다.

 

준영이의 현재 위치를 나타내는 벡터(Vn)가 있을 때,

1분 후 준영이의 위치를 나타내는 벡터(Vn+1)를 구할 수 있을까?

vector <int> Vn = { a, b, c, d, e, f, g, h};
int mat[8][8] = {
	{0, 1, 1, 0, 0, 0, 0, 0},
	{1, 0, 1, 1, 0, 0, 0, 0},
	{1, 1, 0, 1, 1, 0, 0, 0},
	{0, 1, 1, 0, 1, 1, 0, 0},
	{0, 0, 1, 1, 0, 1, 1, 0},
	{0, 0, 0, 1, 1, 0, 0, 1},
	{0, 0, 0, 0, 1, 0, 0, 1},
	{0, 0, 0, 0, 0, 1, 1, 0}
};

Vn과 mat을 곱하면 Vn+1이 나올 것이다.

필요한 만큼(D)를 곱하면 V₁로부터 Vn을 구할 수 있을 것이다.

그런데 계산량이 더 많아졌다.

행렬 곱셈을 D번하므로 D x 8³ 번의 연산이 필요하다. 와우

하지만 우리는 같은 행렬 mat을 여러 번 곱하고 있다.

 

분할 정복

행렬 mat을 D번 곱하는 것만은 피하고 싶다.

만약 D가 2022일 때,

D를 200번 곱하는 것이 아니라 D의 1011 제곱을 구해 그 값을 제곱하면 어떨까?

연산량이 2022 => 2 + a(D의 1011제곱을 구하는 연산량)이 될 것이다.

a가 98보다 작으면 이득이다 야호

 

D의 1011 제곱은 어떻게 구할까?

1010과 1로 분할해서 구하면 될 것 같다.

1010은 505, 505는 504와 1, 504는 252...

... 14, 7, 6, 3, 2 확연히 1011개보다는 적을 것 같다.

 

정리해보면,

지수가 짝수면 지수를 반으로 나눈 행렬을 구해 제곱한다.

지수가 홀수면 지수-1의 행렬과 지수가 1인 행렬을 곱한다.

지수가 대략 반씩 줄어들 것이므로,

D가 10억일 경우라도, 100개보단 적게 구해도 될 것 같다. (이 문제의 경우는 38개를 구한다)

 

이제 우리는 중복해서 계산하지 않도록, 계산한 행렬을 기억하기만 하면 된다.

본인은 map을 이용했다.

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

#include <map>
#include <vector>
using ll = long long;
map<int, vector<vector<ll> > > cache;

ll Q = 1'000'000'007;
vector<vector<ll> > mat_multi(const vector<vector<ll> >& A, const vector<vector<ll> >& B){
	int N = A.size();
	vector<vector<ll> > ret;
	for(int i=0; i<N; i++){
		vector<ll> tmp(N, 0);
		for(int k=0; k<N; k++){
			for(int j=0; j<N; j++){
				tmp[k] += (A[i][j] * B[j][k])%Q;
				if(tmp[k] >= Q){
					tmp[k] %= Q;
				}
			}
		}
		ret.push_back(tmp);
	}
	return ret;
}
vector<vector<ll> > dp(int time){
	if(cache.find(time) !=cache.end()){
		return cache[time];
	}else{
		if(time % 2 == 0){
			return cache[time] = mat_multi(dp(time/2), dp(time/2));
		}else{
			return cache[time] = mat_multi(dp(time-1), dp(1));
		}
	}
}

int mat[8][8] = {
	{0, 1, 1, 0, 0, 0, 0, 0},
	{1, 0, 1, 1, 0, 0, 0, 0},
	{1, 1, 0, 1, 1, 0, 0, 0},
	{0, 1, 1, 0, 1, 1, 0, 0},
	{0, 0, 1, 1, 0, 1, 1, 0},
	{0, 0, 0, 1, 1, 0, 0, 1},
	{0, 0, 0, 0, 1, 0, 0, 1},
	{0, 0, 0, 0, 0, 1, 1, 0}
};
void init(){
	vector<vector<ll> > one;
	for(int i=0; i<8; i++){
		vector<ll> tmp(8);
		for(int j=0; j<8; j++){
			tmp[j] = mat[i][j];
		}
		one.push_back(tmp);
	}
	cache[1] = one;
}
int main() {
	fio;
	int D; cin >> D;
	init();
	vector<vector<ll> > ans = dp(D);
	cout << ans[0][0];
	return 0;
}