[백준] 10830 C++ 행렬 제곱 [분할 정복]

- 문제 설명

 

 

- 문제 풀이

분할 정복을 이용한 거듭제곱을 활용해야 하는 문제이다.

우선 기본적으로 행렬의 곱셈을 어떻게 하는지를 이해하자면

출처 :https://mathbang.net/562#gsc.tab=0

그림과 같이 A행렬과 B행렬이 있다면

1.A행렬의 크기 (m x k)

2. B행렬의 크기 (k x n)

즉 A의 열의 갯수(k)와 B의 행의 갯수(k)가 같아야 곱셈이 성립된다. 그러면 새로운 행렬의 크기 (m x n)가 생기게 되고 이 행렬이 결과값이라고 할 수 있다.

즉 행렬의 거듭제곱은 하나의 행렬을 곱하는 것이므로 행과 열의 크기가 같아야 한다.

 

출처 : https://mathbang.net/562#gsc.tab=0

이 때 단순히 거듭제곱 수(B) 만큼 곱셈을 반복하게 되면, B의 범위는 1 <= B <= 100,000,000,000 이므로 시간초과가 날게 뻔하므로 거듭제곱의 규칙을 이용해야 한다.

 

예를 들어 B = 10 이라고 가정 한다면

 

1. A^10 = A^5 x A^5

2. A^5 = A^2 x A^2 x A

3. A^2 = AxA

4. A = Ax1

 

이런식으로 반으로 나누며 지수 형태로 시간복잡도를 아낄 수 있다. (while ( B > 0) 코드)

 

 

- 코드

#include <iostream>
using namespace std;

long long N, B, mod = 1000;
long long A[5][5];
long long tmp[5][5];
long long ans[5][5];

// 행렬 곱셈
void Matrix_multi(long long x[5][5], long long y[5][5])
{
	for(int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
		{
			tmp[i][j] = 0; // 행렬 초기화
			for (int k = 0; k < N; k++) // x행렬과 y행렬의 곱셈값
				tmp[i][j] += x[i][k] * y[k][j];

			tmp[i][j] %= mod;
		}

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			x[i][j] = tmp[i][j];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> B;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			cin >> A[i][j];
		ans[i][i] = 1; // 정답행렬 단위행렬로 초기화
	}

	while (B > 0) // 10 -> 5 -> 2 -> 1
	{
		if (B % 2 == 1) // ans : a^2 (B=5) -> a^2*a^8 (B=1)
			Matrix_multi(ans, A); // 정답 행렬에 A행렬 곱하기
		Matrix_multi(A, A); // a : a*a (B=10)-> a^2*a^2 (B=5)-> a^4*a^4 (B=2) -> a^8*a^8(B=1)
		B /= 2;
	}

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

	return 0;
}