백준 12850 본대 산책 2 (c++) : 피너클

12850번: 본대 산책2

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

 

이건 이해하는것부터 힘들었다.

/*

정보과학관 : 0
전산관 : 1
신양관 : 2
미래관 : 3
진리관 : 4
한경직기념관 : 5
학생회관 : 6
형남공학관 : 7

*/

long long m[8][8] = {
	{0, 1, 0, 1, 0, 0, 0, 0},
	{1, 0, 1, 1, 0, 0, 0, 0},
	{0, 1, 0, 1, 1, 1, 0, 0},
	{1, 1, 1, 0, 0, 1, 0, 0},
	{0, 0, 1, 0, 0, 1, 1, 0},
	{0, 0, 1, 1, 1, 0, 0, 1},
	{0, 0, 0, 0, 1, 0, 0, 1},
	{0, 0, 0, 0, 0, 1, 1, 0}
};

먼저 배열로 그래프를 그려줬다.

m[1][2] = 1이라면 1에서 2로 가는 경로가 있다는 의미이다.

그리고 m[1][2]가 1이라면 m[2][1]도 무조건 1이다.

 

문제에서는 모든 경로를 구해야 한다.

나는 정보과학관을 0으로 했으니 0에서 시작해 0으로 도달하는 경로의 수를 구해야 한다.

 

그건 m[0][0]이다. 0에서 0으로 가는 경로의 수 말이다.

m[1][2]는 1에서 2로 가는 경로의 수이니 [0][0]도 말이 된다.

이제 뭘 구해야 하는지는 알아냈다. m[0][0]를 구해야한다. 어떻게 구할까?

 

우리에게 2분이 있어서 2번 움직일수있다 생각해보자.

 

예를 들어

0에서 1로 이동한 다음 1에서 0으로 이동할 수 있을 것이다.

그럼 m[0][0]은 0에서 1로 이동하는 경로 * 1에서 0으로 이동하는 경로이다.

 

이걸 행렬의 곱셈으로 표현할수있다.

 

long long m[8][8] = {
	{0, 1, 0, 1, 0, 0, 0, 0},
	{1, 0, 1, 1, 0, 0, 0, 0},
	{0, 1, 0, 1, 1, 1, 0, 0},
	{1, 1, 1, 0, 0, 1, 0, 0},
	{0, 0, 1, 0, 0, 1, 1, 0},
	{0, 0, 1, 1, 1, 0, 0, 1},
	{0, 0, 0, 0, 1, 0, 0, 1},
	{0, 0, 0, 0, 0, 1, 1, 0}
};

위의 행렬에서 m[0][0 ~ 7]은 0에서 출발해서 0 ~ 7으로 가는 경로들이다.

m[0 ~ 7][0]은 0~7에서 출발해 0으로 가는 경로들이다.

 

그럼 m[0][1] * m[1][0] + m[0][2] * m[2][0] + ... + m[0][7] * m[7][0]을 하면 

우리에게 시간이 2분 있을때 0에서 출발해 0으로 이동하는 모든 경로를 알수있게 된다.

 

for (int i = 0; i < 8; i++) {
	for (int j = 0; j < 8; j++) {
		for (int k = 0; k < 8; k++) {
			v[i][j] = (v[i][j] + a[i][k] * b[k][j]) % MOD;
		}
	}
}

코드로 표현하면 이런 느낌이다.

위의 행렬은 대각선을 기준으로 대칭이니 위의 코드가 성립된다.

 

정리하면

long long m[8][8] = {
	{0, 1, 0, 1, 0, 0, 0, 0},
	{1, 0, 1, 1, 0, 0, 0, 0},
	{0, 1, 0, 1, 1, 1, 0, 0},
	{1, 1, 1, 0, 0, 1, 0, 0},
	{0, 0, 1, 0, 0, 1, 1, 0},
	{0, 0, 1, 1, 1, 0, 0, 1},
	{0, 0, 0, 0, 1, 0, 0, 1},
	{0, 0, 0, 0, 0, 1, 1, 0}
};

이 행렬에다가 똑같은 행렬로 행렬의 곱셈을 적용하면 모든 경로에 대한 수가 나오는 것이다.

 

근데 이걸 1,000,000,000 이만큼 하면 시간이 오래 걸릴 것이다.

그래서 우리는 보다 더 빨리 할수있는 방법이 필요하다.

 

5^7를 구한다고 하면 5 * 5 * 5 * 5 * 5 * 5 * 5가 아닌(5 ^ 3) ^ 2 * 5를 하면 더 빨리 구할수있다.

 

행렬도 마찬가지다.

 

행렬을 m이라고 한다면m ^ 10 -> (m^5) ^ 2 -> ((m^2) ^ 2 + 1) ^ 2가 된다.원래 10번을 곱해야 했던 것보다는 매우 빨라졌다.

 

다시 정리하면우리는 행렬의 곱셈을 통해 경로의 경우의 수를 구할수 있고거듭제곱을 더욱 빨리 하는 방법으로 시간안에 답을 구할수있다.

 

long long d, MOD = 1000000007;
vector<vector<long long>> graph;

/*

정보과학관 : 0
전산관 : 1
신양관 : 2
미래관 : 3
진리관 : 4
한경직기념관 : 5
학생회관 : 6
형남공학관 : 7

*/

long long m[8][8] = {
	{0, 1, 0, 1, 0, 0, 0, 0},
	{1, 0, 1, 1, 0, 0, 0, 0},
	{0, 1, 0, 1, 1, 1, 0, 0},
	{1, 1, 1, 0, 0, 1, 0, 0},
	{0, 0, 1, 0, 0, 1, 1, 0},
	{0, 0, 1, 1, 1, 0, 0, 1},
	{0, 0, 0, 0, 1, 0, 0, 1},
	{0, 0, 0, 0, 0, 1, 1, 0}
};

사용할 변수들이다.

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	for (int i = 0; i < 8; i++) {
		vector<long long> tmp;
		for (int j = 0; j < 8; j++) {
			tmp.push_back(m[i][j]);
		}
		graph.push_back(tmp);
	}

	cin >> d;
	cout << solve(d) << '\n';
}

위의 m을 graph에 전부 넣어주고 solve(d)를 돌리면 끝이다.

long long solve(long long time) {
	vector<vector<long long>> result (8, vector<long long>(8, 0));
	for (int i = 0; i < 8; i++) result[i][i] = 1;

solve에서는 거듭제곱을 빨리하는 그 방법을 사용한다.

result는 단위행렬이다.

전부 0인데 가운데 대각선만 1인 행렬이다.

이 행렬에 다른 행렬을 곱하면 행렬이 그대로 출력된다.

 

[1 0 0]   [1 1 0]    [1 1 0]
[0 1 0] * [1 0 1] -> [1 0 1]
[0 0 1]   [0 0 1]    [0 0 1]

위처럼 말이다.

 

long long solve(long long time) {
	vector<vector<long long>> result (8, vector<long long>(8, 0));
	for (int i = 0; i < 8; i++) result[i][i] = 1;

	while (time > 0) {
		if (time % 2 == 0) {
			graph = matrix(graph, graph);
			time /= 2;
		}
		else {
			result = matrix(graph, result);
			time -= 1;
		}
	}
	return result[0][0] % MOD;
}

그 뒤로는 거듭제곱을 해주면 된다.

time이 짝수라면 그대로 행렬끼리 곱을 하고

time이 홀수라면 result와 행렬을 곱해준다.

 

마지막에 result[0][0]를 return하면 끝이다.

 

예를 위해 행렬이 아닌 그냥 수의 거듭제곱을 한다 생각해보자. 

5^7을 한다고 생각하자. 여기서 graph는 5이고 d는 7이다.

 

d가 7이니 홀수이고 result에 곱해야한다. 여기서 result는 1이다.

reulst = result(1) * graph(5) = 5, result는 5가 되고 d는 6이 된다.

result = 5, d = 6

 

이제 d는 6이니 짝수이고 graph끼리 곱해야한다.

graph = graph(5) * graph(5) = 5^2, result는 5, graph는 5^2, d는 3이된다.

result = 5, graph = 5^2, d = 3

 

d는 3이니 홀수이고 result에 곱해줘야한다.

result = result(5) * graph(5^2) = 5^3

result = 5^3, graph = 5^2, d = 2

 

d는 2이니 graph끼리 곱해준다.

graph = graph(5^2) * graph(5^2) = 5^4

result = 5^3, graph = 5^4, d = 1

 

이제 d는 홀수이니 d-1 = 0이 되고 이 계산이 마지막이 된다.

result = result * graph = 5^7

 

이런식으로 진행된다.

long long solve(long long time) {
	vector<vector<long long>> result (8, vector<long long>(8, 0));
	for (int i = 0; i < 8; i++) result[i][i] = 1;

	while (time > 0) {
		if (time % 2 == 0) {
			graph = matrix(graph, graph);
			time /= 2;
		}
		else {
			result = matrix(graph, result);
			time -= 1;
		}
	}
	return result[0][0] % MOD;
}

똑같이 result와 graph를 해주는 것이다.

vector<vector<long long>> matrix(vector<vector<long long>> a, vector<vector<long long>> b) {
	vector<vector<long long>> v(8, vector<long long>(8, 0));
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			for (int k = 0; k < 8; k++) {
				v[i][j] = (v[i][j] + a[i][k] * b[k][j]) % MOD;
			}
		}
	}
	return v;
}

행렬의 곱은 위처럼 구하면 된다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

long long d, MOD = 1000000007;
vector<vector<long long>> graph;

/*

정보과학관 : 0
전산관 : 1
신양관 : 2
미래관 : 3
진리관 : 4
한경직기념관 : 5
학생회관 : 6
형남공학관 : 7

*/

long long m[8][8] = {
	{0, 1, 0, 1, 0, 0, 0, 0},
	{1, 0, 1, 1, 0, 0, 0, 0},
	{0, 1, 0, 1, 1, 1, 0, 0},
	{1, 1, 1, 0, 0, 1, 0, 0},
	{0, 0, 1, 0, 0, 1, 1, 0},
	{0, 0, 1, 1, 1, 0, 0, 1},
	{0, 0, 0, 0, 1, 0, 0, 1},
	{0, 0, 0, 0, 0, 1, 1, 0}
};

vector<vector<long long>> matrix(vector<vector<long long>> a, vector<vector<long long>> b) {
	vector<vector<long long>> v(8, vector<long long>(8, 0));
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			for (int k = 0; k < 8; k++) {
				v[i][j] = (v[i][j] + a[i][k] * b[k][j]) % MOD;
			}
		}
	}
	return v;
}

long long solve(long long time) {
	vector<vector<long long>> result (8, vector<long long>(8, 0));
	for (int i = 0; i < 8; i++) result[i][i] = 1;

	while (time > 0) {
		if (time % 2 == 0) {
			graph = matrix(graph, graph);
			time /= 2;
		}
		else {
			result = matrix(graph, result);
			time -= 1;
		}
	}
	return result[0][0] % MOD;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	for (int i = 0; i < 8; i++) {
		vector<long long> tmp;
		for (int j = 0; j < 8; j++) {
			tmp.push_back(m[i][j]);
		}
		graph.push_back(tmp);
	}

	cin >> d;
	cout << solve(d) << '\n';
}

전체 코드다.