백준[10830] - 행렬 제곱

문제

백준 10830 문제 보기

접근 방법

분할 정복으로 풀긴했지만 뭔가 삽질을 좀 많이한 문제다. 원인은 입력값을 제대로 신경쓰지 않았기때문이다.
1000으로 행렬이 들어올 경우 제곱되는 B의 값이 1이라면 출력은 0으로 나와야하지만 1000으로 그대로 출력해 삽질 좀 했다.
풀이 과정은 지수 법칙을 이용했다. B가 너무 크므로 행렬의 곱을 B번 진행한다면 당연히 시간초과가 난다. 따라서 A^8 == (A^4)^2 == ((A^2)^2)^2 이와 같은 속성을 이용해 문제를 해결할 수 있었다.

코드

#include <iostream>
#include <vector>

using namespace std;

int N;
long long B;
int arr[6][6];

vector<vector<int>> mul(long long sq) {
    vector<vector<int>> ans(N, vector<int>(N));
    vector<vector<int>> c(N, vector<int>(N));
    // 제곱수가 1
    if(sq == 1) {
        for(int i = 0; i < N; i ++) {
            for(int j = 0; j < N; j ++) {
                c[i][j] = arr[i][j] % 1000;
            }
        }

        return c;
    // 제곱수가 짝수
    } else if(sq%2 == 0) {
        // 현재 제곱수의 2로 나눈 숫자를 c에 저장
        c = mul(sq/2);

        // 행렬 c*c 진행
        for(int i = 0; i < N; i ++) {
            for(int j = 0; j < N; j ++) {

                for (int k = 0; k < N; k ++) {
                    ans[i][j] += c[i][k] * c[k][j];
                }
                ans[i][j] %= 1000;
            }
        }

        return ans;
    // 제곱수가 홀수
    } else {
        c = mul(sq-1);

        // 행령 c*arr 진행
        for (int i = 0; i < N; i ++) {
            for (int j = 0; j < N; j ++) {

                for (int k = 0; k < N; k ++) {
                    ans[i][j] += c[i][k] * arr[k][j];
                }
                ans[i][j] %= 1000;
            }
        }
        return ans;
    }
}

int main() {
    cin >> N >> B;

    vector<vector<int>> ans(N, vector<int>(N));

    for(int i = 0; i < N; i ++) {
        for (int j = 0; j < N; j ++) {
            cin >> arr[i][j];
        }
    }

    ans = mul(B);

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

    return 0;
}