#10830 행렬 제곱

# 문제

# 입력/출력

 

# 풀이

내가 작성한 코드는 아래와 같음

#include <iostream>
using namespace std;
const int mod = 1000;
int mat[5][5];
int result[5][5];
int fin[5][5];

void cal(int N) {
	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 += result[i][k] * mat[k][j];
			}
			fin[i][j] = temp % mod;
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			result[i][j] = fin[i][j];
		}
	}
}

int main() {
	int N;
	long long B;
	cin >> N >> B;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> mat[i][j];
			result[i][j] = mat[i][j];
		}
	}
	for (int i = 0; i < B-1; i++) {
		cal(N);
	} 
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << result[i][j] << " ";
		}
		cout << "\n";
	}
}

이렇게 코드를 작성하니 시간 초과가 뜸

그래서 구글링해봤더니

이 부분에서 시간 초과가 나는 것 같다

아무래도 B의 범위가 1 ≤ B ≤ 100,000,000,000 다 보니 시간 초과가 뜨는 것 같음

그래서 찾아보니

위와 같은 알고리즘을 찾았다

 

위의 글만 읽고는 이해가 힘들어서 빠른 거듭제곱 알고리즘을 다시 찾아봤다

https://namnamseo.tistory.com/entry/%EB%B9%A0%EB%A5%B8-%EA%B1%B0%EB%93%AD%EC%A0%9C%EA%B3%B1

빠른 거듭제곱

위의 알고리즘을 참고해서 아래 코드 작성

 

코드는 아래 블로그 참고

https://seokjin2.tistory.com/9

[백준 10830번] 행렬 제곱 - (빠른 거듭제곱 알고리즘)

#include <iostream>
using namespace std;
long long N, B;
long long mat[5][5]; // 입력받은 행렬 값 저장
long long res[5][5]; // 결과값 저장 행렬
long long temp[5][5]; // 중간 계산 값 저장 행렬

void mul_mat(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; // 1000으로 나눈 나머지 저장
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			x[i][j] = temp[i][j];
		}
	}
}

int main(){
	cin >> N >> B;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> mat[i][j];
			res[i][i] = 1; // 단위행렬로 초기화
		}
	}
	while (B != 0) { 
		if (B % 2 == 1) { // 제곱해야 하는 수가 홀수면
			mul_mat(res, mat); // {mat^(2n)}*mat -> 2n은 따로 계산하고 mat만 일단 결과 행렬에 곱셈 진행
		}
		mul_mat(mat, mat); // 2n은 n번 계산해서 제곱(^2)해주면 되기 때문에
		B /= 2; // n번만 계산하기 위해? 행렬은 곱셈 진행하고 2를 계속해서 나눠줌
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << res[i][j] << " ";
		}
		cout << "\n";
	}
}

성공ㅋㅋ