백준 10830번 - 행렬 제곱

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

10830번: 행렬 제곱

 

행렬 제곱 DP를 공부하기 위해 먼저 이 문제를 풀어보았다.

 

주어진 조건 중  "1 ≤ B ≤ 100,000,000,000"을 보고 저게 내 통장 잔고였음 좋겠다...

뻘 생각 한번 해주고 시간 복잡도는 O(logN)으로 구해야겠다 싶었다.

 

내가 문제를 보고 생각했던 logN 풀이는 반드시 (A^2)*(A^2) = A^4를 만족해야 했다.

 

나는 행렬을 고등학교때 배우고 온 세대가 아니기 때문에(나름 신생아^^)

행렬의 곱셈이 어떤 성질을 갖는지 잘 몰랐다.

 

그래서 이게 맞는지 확인하기 위해서 직접 곱해보았다..

 

음.. 맞네요 ㅎㅎ

 

그럼 재귀적으로 풀면 해결할 수 있겠다!

 

여기서 살짝 고민했던 건 사실 함수의 반환 값으로 2차원 배열을 반환하게 하면 더 짧게 코드를 짤 수 있는데 2차원 배열을 반환 값으로 써본 적이 없어서..

 

이렇게 생각한 후에 구현 자체는 어렵지 않았다.

 

구현

 

b가 홀수라면 A^(b/2)*A(b/2)*A 이고

b가 짝수라면 A^(b/2)*A(b/2)이다.

 

이를 기억하고 재귀적으로 함수를 구현하면 된다.

 

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

ll n, b, x;
ll A[7][7]; ll arr[7][7];

void squared(ll a[][7], ll b[][7]) {
    ll temp[7][7];
    memset(temp, 0, sizeof(temp));
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            for (ll k = 0; k < n; k++) {
                temp[i][j] += a[i][k] * b[k][j];
                temp[i][j] = temp[i][j] % 1000;
            }
        }
    }
    memcpy(arr, temp, sizeof(arr));
}

void solve(ll x) {
    if (x == 1) {
        return;
    }
    if (x % 2 == 1) { // 홀수라면
        solve(x / 2);
        squared(arr, arr);
        squared(arr, A);
    }
    else { // 짝수라면 
        solve(x / 2);
        squared(arr, arr);
    }
}

int main() {
    cin >> n >> b;
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            cin >> x;
            A[i][j] = x % 1000;
            arr[i][j] = A[i][j];
        }
    }
    solve(b);
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            cout << arr[i][j] << " ";
        }
        cout << "\n";
    }
}

이렇게 코드를 짜는 걸 분할 정복 기법이라고 한다는데

음.. 그런가 보다ㅎㅎ