7) 백준 10830 - 행렬 제곱

10830번: 행렬 제곱 (acmicpc.net)

10830번: 행렬 제곱

---

지옥 같았던 문제.....

#include <bits/stdc++.h>

using namespace std;

vector<vector<long long> > temp_power(vector<vector<long long> > &tempA, vector<vector<long long> > &tempB, int N) {
	vector<vector<long long> > power_temp(5, vector<long long>(5, 0));
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			int temp = 0;
			for(int k = 0; k < N; k++) {
				temp += tempA[i][k] * tempB[k][j];
			}
			power_temp[i][j]= temp;
		}
	}
	
	return power_temp;
}

vector<vector<long long> > power(vector<vector<long long> > &A, int N, long long B){
	if(B == 1) {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				A[i][j] %= 1000;
			}
		}
		return A;
	}
	vector<vector<long long> > temp(5, vector<long long>(5, 0));
	temp = power(A, N, B/2);
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			temp[i][j] %= 1000;
		}
	}
	if(B % 2 == 0) {
		temp = temp_power(temp, temp, N);
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				temp[i][j] %= 1000;
			}
		}
		
		return temp;
	}
	else {
		temp = temp_power(temp, temp, N);
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				temp[i][j] %= 1000;
			}
		}
		temp = temp_power(temp, A, N);
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				temp[i][j] %= 1000;
			}
		}
		return temp;
	}
	
}
int main(void) {
	int N;
	long long B;
	vector<vector<long long> > A(5, vector<long long>(5, 0));
	cin >> N >> B;
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			cin >> A[i][j];
		}
	}
	vector<vector<long long> > temp(5, vector<long long>(5, 0));
	temp = power(A, N, B);
	
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			cout << temp[i][j] << " ";
		}
		cout << endl;
	}
	
}

1. B의 자릿수를 생각 안함.

 - 왜이리 틀리나 했더니 B입력을 int로 받았다....

2. 2차 배열은 왜 안될까 모르겠다.

 - 모든 배열들을 Vector로 바꾸니 문제가 풀렸다.

 - 2차 배열을 return 받고 나니까 숫자가 다 이상하게 변했다. (이거 때문에 시간 너무 많이 씀...)

 

이걸 이틀이나 걸렸다니.. 배열을 벡터로 바꾸는 생각이 뒤늦게 나버렸다...ㅜㅜㅜㅜㅜ

그래도 결국엔 풀었다. 음하하하