[C++] 백준 10830번: 행렬 제곱 (분할 정복)

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

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

크기가 N x N인 행렬을 B제곱한 결과를 구하여라. 각 원소는 1000으로 나눈 나머지를 취한다.

---

시간복잡도 어림하기

단순 계산 알고리즘

 먼저 단순한 행렬 계산식부터 생각해 봅시다. 기본적인 행렬 계산 알고리즘은 O(n^3)의 시간복잡도를 가집니다. 행렬 M1, M2가 있다고 했을 때, M1의 각 행과 M2의 각 열에 대응하는 원소를 모두 곱해 더해야하고, 이 과정을 M1의 모든 행에 대해 반복해야 하기 때문입니다.

 하지만 문제의 B의 최댓값은 1,000,000,000,000 으로 1조에 해당하는 큰 수입니다. 당연히 이를 제한 시간에 해결할 수 없으므로 다른 방법을 사용해야 합니다.

분할 정복 알고리즘

 하나의 행렬을 제곱하는 데 초점을 더 맞춰 봅시다. 지수법칙에 의해 A의 e제곱은 A의 e / 2 제곱 x A의 e / 2 제곱으로 나타낼 수 있습니다.(e는 짝수라고 가정했습니다.) 이처럼 어떤 수의 e 제곱은 e / 2제곱을 두 번 곱하는 것으로 표현할 수 있습니다. 즉, 동일한 두 제곱의 곱으로 표현할 수 있습니다.

 이때, e / 2 제곱을 한 번 구해두면 다시 e / 2 제곱을 구할 필요가 없습니다. 따라서 각 제곱 수당 한 번만 계산하게 됩니다. 제곱 수의 지수는 2로 나눈 반씩 줄어들기 때문에 어떤 수의 제곱을 구하는 횟수는 logB번이 됩니다. 이후 구한 제곱수를 기반으로 행렬 곱 계산을 진행하므로 총 시간 복잡도는 O(n^3 x logB)입니다. 문제에서 n의 최댓값은 5이고, log(1조)의 값은 대략 40이므로 제한 시간 내에 문제를 해결하기 충분한 수치입니다.  

---

알고리즘 설계하기

 먼저 분할 정복을 사용하지 않고, 재귀 호출을 통해 알고리즘을 먼저 설계해보겠습니다.

 재귀 호출의 결과로 행렬 A의 e제곱이 반환되어야 하기 때문에 2차원 배열을 반환해야 합니다. 저는 구현의 간편성을 위해 vector를 두 개 중첩하여 사용했습니다. vector<vector<int>> 를 여러번 반복하기는 번거롭기 때문에 이후 이 타입을 vvi로 작성하겠습니다. 

* x(곱하기)는 행렬의 곱을 표현한 식입니다. 실제 코드에서 사용하는 표현이 아닙니다.

vvi solve(ll e){
    //기저 조건
    if(e가 1) return a; 
    if(e가 2){
        return a x a;
    }
    if(e가 홀수){
        return a x solve((e - 1) / 2) x solve((e - 1) / 2);
    }
    else{ //e가 짝수
        return solve(e / 2) x solve(e / 2);
    }
}

 먼저 재귀 호출의 종료 지점인 기저 조건을 작성해주었고, e의 값이 홀수인지 짝수인지 판단하여 적절한 곱셈연산을 수행하도록 했습니다.
 e가 홀수인 경우에는 먼저 a를 따로 빼 a x a^(e-1)로 식을 변환합니다. 이때, e - 1은 짝수이므로 e - 1을 2로 나누어 지수 연산을 분할합니다. e가 짝수인 경우에는 바로 e / 2로 분할하여 연산하는 로직입니다.

 하지만, 위 코드에는 문제점이 있습니다. 문제에서 B의 최댓값이 1조이고 B의 값이 반씩 줄어드므로 solve의 깊이는 logB입니다. 이를 최댓값으로 계산하면 대략 40입니다. 위 코드를 보면 한 깊이에서 두 개의 재귀 호출을 진행합니다. 즉 전체 solve 함수를 호출하는 횟수는 2^40으로 1조번 실행하게 됩니다. 따라서 위 로직을 그대로 사용할 수 없습니다.

그렇다면 어떻게 해결할 수 있을까요? 시간복잡도 어림 단계에서 잠깐 이야기했지만. 같은 연산이 중복되는 구조이므로 한 연산의 결과를 한 변수에 따로 저장해두어 중복되는 계산이 없도록 하면 됩니다. 이 로직을 반영한 로직은 다음과 같습니다.

vvi solve(ll e){
    //기저 조건
    if(e가 1) return a; 
    if(e가 2){
        return a x a;
    }
    if(e가 홀수){
        vvi t = solve((e - 1) / 2);
        return a x t x t;
    }
    else{ //e가 짝수
        vvi t = e / 2;
        return t x t;
    }
}

 이와 같이 수정하면 한 깊이당 한 번의 재귀호출만 진행하므로 solve 함수를 호출하는 횟수는 logB번이 됩니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

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

typedef long long ll;
typedef vector<vector<int>> vvi;
ll n, b;
vvi a, ret;

//두 행렬의 곱셈 결과 반환
vvi mul(vvi m1, vvi m2){
    vvi t;
    for(int i = 0; i < n; i++){ //m1의 행만큼 반복
        vector<int> tt;
        for(int j = 0; j < n; j++){ //m2의 열만큼 반복
            int sum = 0;
            for(int k = 0; k < n; k++){ //m1의 행과 m2의 열에서 대응하는 위치 지정
                sum += m1[i][k] * m2[k][j];
            }
            tt.push_back(sum % 1000);
        }
        t.push_back(tt);
    }
    return t;
}
vvi solve(ll e){
    //기저 조건
    if(e == 1) return a;
    if(e == 2){
        return mul(a, a);
    }
    if(e % 2 == 1){ //e가 홀수
        vvi t = solve((e - 1) / 2);
        return mul(a, mul(t, t));
    }
    else{ //e가 짝수
        vvi t = solve(e / 2);
        return mul(t, t);
    }
}
int main(){
    cin >> n >> b;
    int num;
    //행렬 입력
    for(int i = 0; i < n; i++){
        vector<int> vnum;
        for(int j = 0; j < n; j++){
            cin >> num;
            vnum.push_back(num);
        }
        a.push_back(vnum);
    }
    ret = solve(b);
    for(int i = 0; i < n; i++){
        //마지막에도 % 1000 연산 수행
        for(int j = 0; j < n; j++) cout << ret[i][j] % 1000 << " ";
        cout << '\n';
    }
    return 0;
}

 solve 로직은 이전 단계와 동일하고, 두 행렬의 곱을 반환하는 mul 함수가 추가되었습니다. 손으로 행렬연산을 수행하는 그대로 로직을 작성해서 행렬 곱을 알고 계신 분이라면 쉽게 이해하실 수 있을 것입니다.

 위 코드에서 가장 주의해야 하는 부분은 마지막 최종 ret 행렬을 출력할 때, 각 원소에 % 1000 연산을 수행해야 합니다.

예를 들어, 입력이 다음과 같이 들어왔다고 해봅시다.
2 1
1000 1000
1000 1000
이 입력에 대한 결과는
0 0
0 0 이어야 합니다. 문제에서 각 원소를 1000으로 나눈 나머지를 취한다고 했기 때문입니다.
만약, 마지막 부분에 % 1000연산을 하지 않으면,
solve 함수의 if(e == 1) 조건에 의해 모든 원소가 1000인 행렬이 ret에 들어오고, 이 값 그대로 출력될 것입니다. 따라서 문제를 틀리게 됩니다.

---