[백준 10830][C++] 행렬 제곱

문제

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

10830번: 행렬 제곱

 

 

풀이 과정

분할 정복 알고리즘을 적용한다. 행렬 곱 함수를 작성한 뒤, 행렬의 제곱을 기록하며 결과를 이용하도록 구현한다.

예를 들어 A^9를 구한다고 가정했을 때, A^9 = A * (A^4) * (A^4) 형태로 곱이 이루어지며, O(logN)의 시간 복잡도를 가진다.

 

정답 배열을 초기화할 때는 곱을 해도 원래 형태가 나오도록 단위행렬 형태로 초기화해야 한다.

 

소스 코드

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

long long N,B;

long long A[5][5];
long long ans[5][5];

void mat_mul(long long a[5][5], long long b[5][5]){
    long long temp[5][5];
    memset(temp, 0, sizeof(temp));
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            for(int k=0;k<N;k++){
                temp[i][j] += a[i][k]*b[k][j];
            }
            temp[i][j] = temp[i][j] % 1000;
        }
    }

    memcpy(a,temp,sizeof(temp));
}


int main(){
    cin >> N >> B;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin >> A[i][j];
        }
        ans[i][i]=1;
    }

    while(B>0){
        if(B%2==1){
            mat_mul(ans,A);
        }
        mat_mul(A,A);
        B /= 2;
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cout << ans[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

 

결과 및 후기