백준 10830 (행렬 곱셈) c++

문제

10830번: 행렬 제곱

n * n 행령이 주어지면 b번곱한 행렬을 출력하는 문제입니다

행렬이 너무 커질 수 있으므로 행렬이 모든 값은 1000으로 나눈 나머지입니다.

 

딱 보면 백준 1629  문제와 매우 유사합니다.

분할 정복으로 접근하면 될것 같습니다.

 

여기서 막혔던 것은 분할정복으로 이차원 배열을 return 하는 것이 까다로웠습니다.

int arr[6][6];
int result[6][6];

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

arr배열에는 행렬의 원형만 들어갈 것이고, result 배열에는 계속해서 행렬의 제곱을 업데이트 해줄 것입니다

위의 코드는 입력부분입니다.

recur(b);

void recur(ll ex) {
	if (ex == 1)
		return;
	if (ex % 2 == 1) {
		recur(ex / 2);
		multi(result, result);
		multi(result, arr);
	}
	else {
		recur(ex / 2);
		multi(result, result);
	}
}

main 함수에서 recur(b)를 호출하였습니다.

위의 함수는 주어진 지수를 분할 정복하는 부분입니다.

void multi(int arr1[6][6],int arr2[6][6]) {
	int temp[6][6];
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			temp[k][i] = 0;
			for (int j = 0; j < n; j++) {
				temp[k][i] += (arr1[k][j] * arr2[j][i]);
			}
			temp[k][i] %= 1000;
		}
	}
	memcpy(result, temp, sizeof(result));
}

행렬을 곱하는 부분입니다.

---

전체코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll n, b;
int arr[6][6];
int result[6][6];
void multi(int arr1[6][6], int arr2[6][6]);
void recur(ll ex);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> b;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> result[i][j];
            result[i][j] %= 1000;
            arr[i][j] = result[i][j];
        }
    }
 
    recur(b);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << result[i][j] << ' ';
        }
        cout << '\n';
    }
 
 
 
    return 0;
}
void multi(int arr1[6][6],int arr2[6][6]) {
    int temp[6][6];
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            temp[k][i] = 0;
            for (int j = 0; j < n; j++) {
                temp[k][i] += (arr1[k][j] * arr2[j][i]);
            }
            temp[k][i] %= 1000;
        }
    }
    memcpy(result, temp, sizeof(result));
}
void recur(ll ex) {
    if (ex == 1)
        return;
    if (ex % 2 == 1) {
        recur(ex / 2);
        multi(result, result);
        multi(result, arr);
    }
    else {
        recur(ex / 2);
        multi(result, result);
    }
}