[C++] 10830: 행렬 제곱

 

🖍️ 겪은 문제

• 5 * 5 * 100,000,000,000 = 2조5천억번의 제곱연산...
• 1억번이 1~2초니까 1조번의 연산이면 10000~20000초임(시간초과가 안나는게 이상)

🔍 해결 방법

• 지금은 계속 원본 행렬만 곱하는데 a2 * a = a3.. 이런 식으로 원본 행렬의 제곱끼리 곱하는 방식을 이용하는건 어떨까?
• 단, 2의 제곱수가 아닌 5와 같은 수면 a2 * a2 * a라는 걸 어떻게 계산해서 구하지? log연산을 해야하는건가?
  • 10이면 a4 * a4 * a2
• 2조 5천억은 2의 42제곱이라고 함. 그러니까 연산 횟수를 줄일 수 있을 것 같음.

📇 코드

#include <iostream>
#include <vector>
using namespace std;

int N;
using Matrix = vector<vector<int>>;

Matrix multiply(Matrix& A, Matrix& B) {
    Matrix result(N, vector<int>(N, 0));
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            for (int k=0; k<N; k++) {
                result[i][j] = (result[i][j] + A[i][k] * B[k][j]) % 1000;
            }
        }
    }
    return result;
}

Matrix power(Matrix A, long long exp) {
    if (exp == 1) {
        // 모든 원소를 1000으로 나눠줌
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                A[i][j] %= 1000;
            }
        }
        return A;
    }

    Matrix half = power(A, exp / 2);
    Matrix result = multiply(half, half);
    if (exp % 2 == 1) {
        result = multiply(result, A);
    }
    return result;
}

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

    long long B;
    cin >> N >> B;

    Matrix A(N, vector<int>(N));
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cin >> A[i][j];
        }
    }

    Matrix answer = power(A, B);
    for (const auto& row : answer) {
        for (int val : row) {
            cout << val % 1000 << ' ';
        }
        cout << '\n';
    }
    return 0;
}

📇 시간 초과되었던 기존 코드

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

    int N, B;
    cin >> N >> B;
    vector<vector<int>> v(N, vector<int>(N, 0));
    vector<vector<int>> accuV(N, vector<int>(N, 0));
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cin >> v[i][j];
            accuV[i][j] = v[i][j];
        }
    }

    for (int t=0; t<B - 1; t++) {
        vector<vector<int>> newV(N, vector<int>(N, 0));
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                // i행과 j열 각각의 원소의 곱 더한거
                int sum = 0;
                for (int k=0; k<N; k++) {
                    sum += (accuV[i][k] * v[k][j]) % 1000;
                    // cout << v[i][k] << " * " << v[k][j] << " = " << v[i][k] * v[k][j] << '\n';
                }
                newV[i][j] = sum % 1000;
            }
        }
        accuV = newV;
    }

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