백준 10830번 행렬 제곱

 

 

문제 보러가기 : https://www.acmicpc.net/problem/10830

 

 

10830번: 행렬 제곱

 

 

이번 문제는 분할 정복 문제였습니다.

 

 

 

 

《문제 풀이》

 

1. B의 최댓값이 1000억이므로 long long 자료형으로 선언

2. 2차원 벡터의 공간을 N*N 크기로 할당해줌 --> A(N, vector<int>(N)) 

3. 행렬의 곱을 연산하는 부분은 연산자 오버로딩을 통해 구현

     --> matrix operator * (const matrix &a, const matrix &b)

4. A의 B제곱 연산횟수를 최소화하기 위해 분할 정복 이용 ⭐

5. 지수(B)가 홀수인 경우, 결과 행렬에 밑수(A)를 곱해줌

6. 5번에서 밑수를 하나 빼줬으므로, 지수는 짝수로 바꿔주고(exp / 2) 밑수는 제곱해줌 

 

 

 

 

《C++ 코드》

 

#include <iostream>
#include <vector>

using namespace std;

int N;
typedef long long ll;
typedef vector<vector<int>> matrix;

matrix operator * (const matrix &a, const matrix &b) {
	matrix res(N, vector<int>(N));
	
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			for(int k=0; k<N; k++) {
				res[i][j] += a[i][k] * b[k][j]; 
			}
			res[i][j] %= 1000;
		}
	}
	return res;
}

matrix calc(matrix a, ll exp) {
	matrix res(N, vector<int>(N));
	
	for(int i=0; i<N; i++)
		res[i][i] = 1; // 단위 행렬  
	
	if(exp == 0) 
		return res;
	 	
	if(exp % 2) // 지수가 홀수인 경우 
		res = res * a;
		
	return res * calc(a * a, exp / 2);
} 

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll B;
	cin>>N>>B;
	
	// N*N 크기의 2차원 벡터  
	matrix A(N, vector<int>(N));
	
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++)
			cin>>A[i][j];
	
	matrix res = calc(A, B); // 행렬 A의 B제곱   
	
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			cout<<res[i][j]<<" ";
		}
		cout<<"\n";
	}
		
	return 0;
}

 

 

개발 환경: Dev-C++

 

 

baekjoon - 정답 화면