BOJ - 10830 행렬 곱셈 해결 전략 (C++)

• 문제 링크
  백준 10830번 - 행렬 제곱

해결 전략

  이 문제는 행렬의 성질을 알고 있으면 그닥 어렵지 않게 풀 수 있다. 우선, 입력이 최대 1천억까지 가능하므로, 본능적으로 이 문제는 Divide & Conquer 문제임을 알 수 있다. 행렬의 제곱을 분할 정복하기 위한 기반 수식이 무엇이 있을까?

A^k = A^(k/2) * A^(k/2)

  아스타리스크 기호는 행렬곱을 나타낸다고 하자. 행렬곱은 행렬을 하나의 기호로 나타낼 시 위와 같이 마치 정수 곱셈처럼 쪼개서 나타낼 수 있다. 이 수식을 이용해 분할 정복 방식을 시도할 수 있음을 바로 알 수 있다.

  이 생각을 기반으로 나는 다음과 같은 분할정복 알고리즘을 설계했다.

Threshold 이하는 Naive한 행렬곱 O(n^3)을 수행하면 될 터이고, 그 외에는 재귀호출을 반으로 쪼개서 하되, 중복 호출을 방지하기 위해 한 번만 호출하고, 그 정보를 이용하자!

  상당히 괜찮은 접근이었고, 정답에 거의 가깝게 다가간 방법이었다.

  그런데, 한 가지 실수 아닌 실수를 했다. 그것이 무엇이냐면, 굳이 Threshold를 둔 것이 문제였다. 그냥 입력받은 b가 0이 되기 전까지 (절반끼리의) 행렬곱을 Naive하게 진행해도 문제가 되지 않는데, 굳이 Threshold를 두어 예외처리가 복잡해진 것이다.

  그리고, Threshold를 두지 않으면, 굳이 재귀호출을 할 필요도 없다. 그냥 선형적으로 흐름이 진행되기 때문이다.

그냥 while문으로 exponent b가 0이 되기 전까지 b를 반으로 나눠가면서 a에 대해 행렬곱을 수행하고 그 결과를 a에 계속 업데이트해간다(A^k가 A^2k가 되어간다).
b가 홀수일 때만 res에다가 행렬 곱을 한 번씩 더 해주고, while이 깨지기 전에는 항상 b == 1이므로, 거기서 마지막에 res에 결과를 기억해준다.

  분할 정복을 (특히 흐름이 선형적일 때에는) 굳이 재귀호출로 처리할 필요는 없다는 것을 기억하자. 아래는 코드이다.

#include <iostream>
// BOJ - 10830 Matrix Power
#define DIV	1000
using namespace std;

int a[5][5], temp[5][5], res[5][5];

void naive_matrix_power(int n, int A[][5], int B[][5]) {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			for (int t = 0; t < n; t++) {
				temp[i][j] += (A[i][t] * B[t][j]) % DIV;
				temp[i][j] %= DIV;
			}
		}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			B[i][j] = temp[i][j];
			temp[i][j] = 0;
		}
}

void matrix_power(int n, long long b) {
	while (b > 0) {		
		if (b % 2 == 1) 
			naive_matrix_power(n, a, res);
		naive_matrix_power(n, a, a);

		b /= 2;
	}
}

int main(void) {
	int n; long long b;
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> n >> b;
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) 
	{ cin >> a[i][j]; res[i][j] = a[i][j] % DIV; }
	matrix_power(n, b - 1);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) cout << res[i][j] << ' ';
		cout << '\n';
	}

	return 0;
}