Easy is Perfect

[백준] 10830번 _ 행렬 제곱

  • melonicedlatte
  • Aug 22, 2020


1. 문제

https://www.acmicpc.net/problem/10830

2. 풀이

2.1. int 이중 포인터를 이용한 문제 풀이

  • 행렬의 제곱수를 줄일 때(제곱수는 k라고 해보자)
    • 제곱수가 홀수일 때는 -1을 해주어 $ A^{k - 1} * A $ 로 만들어 제곱수를 짝수로 만들어주고
    • 제곱수가 짝수일 때는 /2를 해주어 $ A^{\frac{k}/{2}} $ 로 만들어 계산량을 줄입니다.
#define _CRT_SECURE_NO_WARNINGS
#include<algorithm>
#include<iostream>
using namespace std;
int n;
long long b;   //거듭제곱 횟수
int m[6][6];   //주어진 행렬

int** mul(int** a, long long k, int** trash) {   //정답행렬, 횟수, 임시행렬 
	if (k == 1) return a;
	if (k == 2) {                        //제곱일때,
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int temp = 0;
				for (int h = 0; h < n; h++)		
					temp += (m[i][h] * m[h][j]) % 1000;
				a[i][j] = temp % 1000;
			}
		}
		return a;
	}


	int** t = mul(a, k / 2, trash);
	for (int i = 0; i < n; i++)     //임시행렬 초기화
		for (int j = 0; j < n; j++)
			trash[i][j] = t[i][j];

	if (k % 2) {   //거듭제곱 == 홀수
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int temp = 0;
				for (int h = 0; h < n; h++)
					temp += (trash[i][h] * m[h][j]) % 1000;
					a[i][j] = temp % 1000;
			}
		}
		return a;
	}
	else {  //거듭제곱 == 짝수
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int temp = 0;
				for (int h = 0; h < n; h++)
					temp += (trash[i][h] * trash[h][j]) % 1000;
				a[i][j] = temp % 1000;
			}
		}
		return a;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> n >> b;
	int** ans = new int*[n]; 
	int** tsh = new int*[n];

	for (int i = 0; i < n; i++)			// 행렬 동적할당
		ans[i] = new int[n], tsh[i] = new int[n];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> m[i][j];
			ans[i][j] = m[i][j] = m[i][j] % 1000;
		}
	}

	ans = mul(ans, b, tsh);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) 
			cout << ans[i][j] << " ";
		cout << "\n";
	}

	for (int i = 0; i < n; i++)			//할당 해제 
		delete[] ans[i], delete[] tsh[i];
	delete[] ans, delete[] tsh; 

	return 0;
}



Search