[백준] 10830 행렬 제곱

문제
크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

입력
첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

출력
첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

예제 입력 1
2 5
1 2
3 4
예제 출력 1
69 558
337 406

Concept

B의 크기가 매우 크므로 Brute Force를 이용할 수는 없을 것이다. n/2씩 나누어 재귀적으로 재호출하는 분할정복을 이용하기로 하자.

Code

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

int** arr;
int n;

//두 행렬을 곱해주는 함수
int** multi(int** arr, int** arr2){
	//int tmp[5][5] = { 0 };
	int** tmp;
	tmp = new int* [n];
	for (int i = 0; i < n; i++) {
		tmp[i] = new int[n];
	}

	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) tmp[i][j] = 0;
		
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				tmp[i][j] += (arr[i][k] * arr2[k][j])%1000;
			}
		}
	}
	return tmp;

}
// 지수를 쪼개어 곱하는 기능 담당
int** pow(long long n){
	if (n == 1) return arr;
	else if (n % 2 == 1) return multi(pow(n-1), arr);
	else {
		int** tmp = pow(n / 2);
		return multi(tmp, tmp);
	}
}


int main() {
	long long b;
	cin >> n >> b;

	
	arr = new int* [n];
	for (int i = 0; i < n; i++) {
		arr[i] = new int[n];
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	int** result = pow(b);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout<< result[i][j]%1000<<' ';
		}
		cout << endl;
	}
}

Comment

생각하기는 쉬운데, 구현이 쉽지만은 않다.
2차원 배열을 넘기기 위해 어쩔 수 없이 동적할당을 진행했다.
초반에 1000으로 나눈 나머지를 구한다는 조건을 보지 못해 불필요한 시간소요가 있었고,

else {
		int** tmp = pow(n / 2);
		return multi(pow(n / 2), pow(n / 2));
	}

위와 같이 pow를 2번 연산한 값을 리턴하면 계산을 쓸데없이 한번 더 하게 되어 시간초과 또는 메모리 초과가 발생했다. 이에 유의하자.