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

문제링크:https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱

 

접근방식

 

1. B가 100,000,000,000 이므로 매번 곱해주는 형식으로는 무조건 시간초과

2. 행렬을 1번 곱하고 그값들로 또 1번 곱하게 되면 기존 행렬을 4번 곱한 것과 같은 형태이다.

즉 행렬곱셉은 제곱연산이 가능한 형태!! 

그러면 dp나 분할정복을 통해서 제곱으로 계산해주는 형태를 생각하게 됨.

3. 제곱값들을 한번씩만 사용해주면 되기 때문에 분할정복을 선택함 

 

문제풀이 

 

1. 아래처럼 분할정복 호출을 구현하는데, 직관적인 코드이다.

ex) b 가 10일 때, (행x행) 하나 생성하고 b는 5로

     b 가 5일 때, (행x행) 을 결과값으로 넣고 그리고 (행x행)X(행x행) 을 생성

     b 가 2일 때,  ((행x행)X(행x행)) X ((행x행)X(행x행)) 생성

     b 가 1일 때,  (행x행) 인 결과값에 ((행x행)X(행x행)) X ((행x행)X(행x행)) 를 곱해줌으로써 (행x행) X ((행x행)X(행x행)) X ((행x행)X(행x행)) 으로 10번 행이 곱해지게끔 만들어주는 방식이다. 

 

이러한 식 도출은 딱히 방식이 있다기 보다는 문제를 많이 풀어보면서 노하우를 습득하는 방법밖에 없는 것 같다.... 

while (b) {
		if (b % 2 == 1) {
			solved(result, arr);
		}
		solved(arr, arr);
		b /= 2;

	}

2. 행렬 곱셈은 원래 아는 방식 그대로 구현

다만, result 초기값을 단위행렬로 구성하는 것을 주의 

 

 

정답코드입니다.

#include <iostream>
using namespace std;

long long n, b;
int arr[5][5];
int result[5][5];
int temp[5][5];

void solved(int v1[5][5], int v2[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] += (v1[i][k] * v2[k][j]);
			temp[i][j] %= 1000;
		}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) 
			v1[i][j] = temp[i][j];
		
			
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> b;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
		result[i][i] = 1;
	}
	while (b) {
		if (b % 2 == 1) {
			solved(result, arr);
		}
		solved(arr, arr);
		b /= 2;

	}


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			cout << result[i][j] << ' ';
		cout << endl;
	}

	return 0;
}