[c++] 백준 10830, 행렬 제곱

백준 10830

알고리즘 분류 : divide and conquer (분할 정복)

크기가 N*N인 행렬 A가 주어졌을 때, A의 B제곱을 구하는 문제다.

B가 1이 될 때까지, 2로 반복해서 나누어 행렬 ans를 구한다.

B%2=1인 경우, solve(ans,A)
B%2=0인 경우, solve(A,A)

solve 함수는 행렬 X와 행렬 Y를 곱하여, 행렬 X에 저장하는 함수다.

#include <iostream>

using namespace std;
long long N,B;
long long A[5][5],ans[5][5],temp[5][5];

void solve(long long X[5][5],long long Y[5][5]){
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			temp[i][j]=0;
			for(int k=0; k<N; k++){
				temp[i][j]+=X[i][k]*Y[k][j];
			}
			temp[i][j]%=1000;
		}
	} //행렬의 곱셈
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			X[i][j]=temp[i][j];
		}
	}
}

int main(){
	ios::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];
		}
		ans[i][i]=1;
	}
	
	while(B){
		if(B%2){
			solve(ans,A);
		}
		solve(A,A);
		B/=2;
	}
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			cout << ans[i][j] << ' ';
		}
		cout << '\n';
	}
}