[C++] BOJ 10830번 : 행렬 제곱

📝 문제

💻 실행 코드

// BOJ 10830번 : 행렬 제곱
#include <iostream>
using namespace std;
void matrix(int a[5][5], int b[5][5]);
long long n, b;
int arr[5][5];
int result[5][5];
int tmp[5][5];


int main() {
    ios::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 >> arr[i][j];
        }
        result[i][i] = 1; // result 배열 초기화
    }

    while(b){ // b가 0이 아닐 떄까지
        if(b % 2 == 1){ // 홀수일 때
            matrix(result, arr);
        }
        matrix(arr, arr); // 짝수일 때
        b /= 2; // 2로 나누기
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cout << result[i][j] << " "; // 배열 출력
        }
        cout << "\n";
    }
}

void matrix(int a[5][5], int b[5][5]){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            tmp[i][j] = 0; // tmp 초기화
            for(int k = 0; k < n; k++){ // a와 b 곱한 값 tmp에 넣기
                tmp[i][j] += a[i][k] * b[k][j];
            }
            tmp[i][j] %= 1000; // 값을 1000으로 나눈 나머지 저장
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            a[i][j] = tmp[i][j]; // tmp의 값을 a배열(result)에 다시 저장
        }
    }
}

📚 문제 풀이

A^n을 A x A x ... A^n 이렇게 곱하면 시간초과

빠른 거듭제곱 알고리즘

• n이 홀수이면 A^n을 A^(n-1)로 바꾸고 A를 결과값에 곱합
• n이 짝수이면 A^n을 A^2^(n/2)로 바꾸고 A를 제곱하고 n을 2로 나눔
• n == 0이면 종료

✅ 실행 결과