BOJ 10830: 행렬 제곱

✔ 문제 링크

BOJ 10830: 행렬 제곱

---

✔ 문제해결전략

• Recursion

---

✔ 해결과정

BOJ 1629: 곱셈에서와 같은 논리로 exponent가 너무 크므로 exp/2 계속 재귀호출하면서 O(log N)으로 바운드 시킨다.

---

✔ 정답 CODE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

using vvll = vector<vector<ll>>;

vvll multiplyMatrix(const vvll& m1, const vvll& m2, int n) {
    vvll result(n, vector<ll>(n));
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            for(int k=0;k<n;k++) {
                result[i][j] += m1[i][k] * m2[k][j];
            }
            result[i][j] %= 1000;
        }
    }
    return result;
}

vvll squareMatrix(const vvll& m, ll exp, int n) {
    if(exp==1) return m;
    vvll ans = squareMatrix(m, exp/2, n);
    ans = multiplyMatrix(ans, ans, n);
    // exp == odd
    if(exp&1) return multiplyMatrix(m, ans, n);
    // exp == even
    return ans;

}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    ll b;

    cin >> n >> b;
    vvll mat(n);
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            int num;
            cin >> num;
            mat[i].push_back(num);
        }
    }
   vvll ans =  squareMatrix(mat,b,n);

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

}

---

✔ Comment

시프 Optimization 단원에서 matrix multiply 관련 예제가 나왔었는데 3중 for문 구조 관련해서 어느 방식이 가장 cache 잘 활용한 방식이었는지 복습하면 너무 알찰 듯