[백준] No.10830 - 행렬 제곱 (C++)

문제

www.acmicpc.net/problem/10830

10830번: 행렬 제곱

 

풀이

행렬 A의 제곱 수인 B는 최대 100,000,000,000의 값을 가지기 때문에 단순히 A를 반복해 곱하는 것은 시간 초과를 발생시킨다. 이와 같이 입력값이 너무 큰 경우 분할 정복을 떠올리자.

 

제곱 수를 pow_num이라고 하면

pow_num %2 ==1 인 경우, 즉 홀수라면 A^(pow_num-1) * A를

 

짝수라면 A^(pow_num/2) * A^(pow_num/2) 로 계산한다면 제곱 연산을 O(logB) 수준으로 줄일 수 있다.

 

단 해당 문제는 B의 최댓값이 int형의 최댓값을 벗어나므로 long long형으로 선언해야하고

 

본인의 경우 원소 값이 한 개라도 1,000이고 B가 1인 경우 1,000으로 나눈 값을 출력하는 예외를 처리하지 못하여 고생했다.

최종적으로 값을 출력할 때도 나누기 연산을 해주자!

 

 

코드

	#include <iostream>
	#include<vector>
	using namespace std;
	int matrix_size;
	long long B;
	vector<vector<int>> matrix_A;
	vector<vector<int>> multiplyMatrix(const vector<vector<int>>& matrix_left,const vector<vector<int>>& matrix_right ){
	vector<vector<int>> result_matrix;
	vector<int> temp_row;
	for(int i=0; i<matrix_size ; ++i){
	temp_row = matrix_left[i];
	vector<int> result_row;
	for(int j=0 ; j<matrix_size ; ++j ){
	vector<int> temp_column;
	for(int k=0; k<matrix_size ; ++k)
	temp_column.push_back(matrix_right[k][j]);
	int result =0;
	for(int k=0; k<matrix_size ; ++k)
	result+= temp_row[k]*temp_column[k];
	result_row.push_back(result%1000);
	}
	result_matrix.push_back(result_row);
	}
	return result_matrix;
	}
	vector<vector<int>> powMatirx(long long pow_num){
	if(pow_num ==1)
	return matrix_A;
	if(pow_num %2 ==1){
	return multiplyMatrix( powMatirx(pow_num-1) , matrix_A );
	}else{
	vector<vector<int>> temp = powMatirx(pow_num/2);
	return multiplyMatrix( temp , temp);
	}
	}
	int main() {
	cin>>matrix_size>>B;
	int temp_num;
	for(int i=0; i<matrix_size ; ++i){
	vector<int> temp_vec;
	for(int j=0; j<matrix_size ; ++j){
	cin>>temp_num;
	temp_vec.push_back(temp_num);
	}
	matrix_A.push_back(temp_vec);
	}
	vector<vector<int>> result_matrix = powMatirx(B);
	for(int i=0; i<matrix_size ; ++i){
	for(int j=0; j<matrix_size ; ++j)
	cout<<result_matrix[i][j]%1000<<' ';
	cout<<'\n';
	}
	return 0;
	}

view raw [BaekJoon]_10830_행렬 제곱.cpp hosted with ❤ by GitHub