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

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

10830번: 행렬 제곱

행렬 제곱을 분할 정복을 통해 푸는 문제입니다.

이 문제를 풀기 위해서는 행렬의 제곱을 할 수 있어야 합니다.

행렬 제곱이 어떻게 계산되는지 2 * 2 / 3 * 3 행렬을 통해 확인해보겠습니다.

2 * 2 / 3 * 3 행렬의 곱셈을 통해, 앞 행렬은 [X][Y] 중 X부분이 바뀌고, 뒤 행렬은 Y부분이 바뀌는 것을 알 수 있습니다.

이를 통해 행렬의 곱셈을 구현할 수 있습니다.

matrix multi(matrix a, matrix b) {
	matrix ans;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int sum = 0;
			for (int k = 0; k < N; k++) {
				sum += a.Data[i][k] * b.Data[k][j];
				sum %= 1000;
			}
			ans.Data[i][j] = sum;
		}
	}
	return ans;
}

 

이제 행렬을 직접 제곱하기만 하면 되는데, B의 범위가 최대 1000억입니다. 

for문을 통해 제곱을 만들면, 시간 초과가 생기기에 다른 방법이 필요합니다.

이때 사용하는 방법이 분할 정복입니다.

N값을 통해 나눠주면서 곱해주면 빠르게 계산할 수 있습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>

using namespace std;

int N;
long long int B;
typedef struct matrix {
	int Data[5][5];
}matrix;
matrix Base;


matrix multi(matrix a, matrix b) {
	matrix ans;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int sum = 0;
			for (int k = 0; k < N; k++) {
				sum += a.Data[i][k] * b.Data[k][j];
				sum %= 1000;
			}
			ans.Data[i][j] = sum;
		}
	}
	return ans;
}

matrix Multiple(matrix x, long long int y) {
	if (y > 1) {
		x = Multiple(x, y / 2);
		x = multi(x, x);
		if (y % 2 == 1) {
			x = multi(x, Base);
		}
	}
	return x;
}

void solve() {
	matrix arr;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr.Data[i][j];
			arr.Data[i][j] %= 1000;
		}
	}
	Base = arr;
	arr = Multiple(arr, B);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << arr.Data[i][j] << " ";
		}
		cout << "\n";
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> B;
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요