BOJ 10830 : 행렬 제곱 [C++]

 

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

10830번: 행렬 제곱

 

문제 요약

주어진 행렬 $A$와 자연수 $B$에 대하여, $A^B$의 각 원소를 1000으로 나눈 나머지를 출력하는 문제이다.

 

해결 전략

어떠한 정수 $A$를 B제곱하는 것은 분할 정복을 이용하여 계산하는 것이 잘 알려져있다.

$A^B = A^{B/2} * A^{B/2}$이고, 

$A^{B/2} = A^{B/4} * A^{B/4}$이고,

...

이렇게 계속해서 B를 절반으로 쪼개어 생각하면 $O(log{B})$에 $A^B$를 구할 수 있다.

 

이 아이디어를 행렬에도 똑같이 적용해보자.

 

위에서 설명했던 $A$를 정수가 아니라 행렬이라고 가정해도,

행렬 연산에서 교환 법칙이 성립하기 때문에 위 등식이 모두 성립한다.

 

따라서 $A^B$를 구하기 위해서, $A^{B/2}$를 구하면 된다.

 

B가 홀수인 경우에는 $A^B = A^{B/2} * A^{B/2} * A$와 같이 계산할 수 있다.

 

분할하는 함수의 반환형을 std::vector<std::vector<int>> 로 해서 2차원 행렬을 반환하도록 구현한다.

 

#include <bits/stdc++.h>
using namespace std;
using vv = vector<vector<int> >;
using ll = long long;
int N;
vv arr;

vv R(ll n) {
	if (n == 1)	return arr;
	vv part = R(n / 2);
	vv conq(N);
	for (int x = 0; x < N; x++) {
		for (int y = 0; y < N; y++) {
			int s = 0;
			for (int i = 0; i < N; i++)
				s += part[x][i] * part[i][y];
			conq[x].push_back(s % 1000);
		}
	}
	if (n % 2) {
		part = conq;
		conq = vv(N);
		for (int x = 0; x < N; x++) {
			for (int y = 0; y < N; y++) {
				int s = 0;
				for (int i = 0; i < N; i++)
					s += part[x][i] * arr[i][y];
				conq[x].push_back(s % 1000);
			}
		}
	}
	return conq;
}

int main() {
	ll B;
	int a;
	cin >> N >> B;
	arr = vv(N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> a;
			arr[i].push_back(a % 1000);
		}
	}
	vv ans = R(B);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)	cout << ans[i][j] << ' ';
		cout << '\n';
	}
}

 

필자는 정수 거듭제곱을 해결할 수 있었음에도 이 문제를 푸는데 반 년 이상이 걸렸다.

풀고 나서 보면 왜 생각 못했나 싶지만 행렬 연산이 머릿속에 복잡하게 생각되어 그랬던 것 같다.