[BOJ] 백준 10830번 - 행렬 제곱 풀이

| |
백준 온라인 저지 10830번 - 행렬 제곱 C++ 재귀 풀이


문제

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.


입력

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.


출력

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.


풀이

애초에 B 의 범위가 int 형을 넘어갈 정도로 크기 때문에 당연히 단순한 방법으로는 시간 초과 가 나온다. 따라서 A^B 의 계산 속도를 비약적으로 높힐 방법을 떠올려야 하는데 여기서 분할정복 을 적용할 수 있다. 아이디어는 다음과 같다.

  • B가 홀수일 경우: A * A^(B-1)
  • B가 짝수일 경우: A^(B/2) * A^(B/2)
  • B가 1일 경우(기저 사례): A 를 그대로 반환

위와 같은 알고리즘을 사용하면 O(logN) 의 시간복잡도로 계산을 완료할 수 있다.

그런데 이 때 중복 계산 이 재귀가 깊어질수록 기하급수적으로 발생하기 때문에 메모이제이션 기법을 이용해 이를 방지해야한다. 행렬을 표현하기 위해 원소로 2차원 배열 을 사용하기 때문에 map 을 이용해 메모이제이션 을 구현해주어야 한다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <vector>
#include <map>
using namespace std;

typedef vector<vector<int>> Matrix;

int N;
long long B;
map<long long,Matrix> cache;

Matrix multipleMatrix(const Matrix& a, const Matrix& b){
    Matrix ret(N,vector<int>(N));
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            for(int k=0;k<N;k++)
                ret[i][j]+=a[i][k]*b[k][j];
            ret[i][j]%=1000;
        }
    }
    return ret;
}

Matrix solve(Matrix& arr, long long n){
    if(n==1) return arr;
    if(cache.find(n) != cache.end()) return cache[n];
    if(n&1) return cache[n] = multipleMatrix(arr,solve(arr,n-1));
    return cache[n] = multipleMatrix(solve(arr,n/2),solve(arr,n/2));
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin>>N>>B;

    Matrix base(N,vector<int>(N));

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

    Matrix ans = solve(base,B);

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

    return 0;
}
0%