[백준] 10830: 행렬 제곱 (C++)

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

10830번: 행렬 제곱

요구사항

---

① 다이나믹 프로그래밍

② 행렬 곱

③ MOD 1000으로 나타내기

④ 분할정복 (시간복잡도 단축)

코드

---

#include <algorithm>
#include <cstring>
#include <iostream>

#define MOD 1000

using namespace std;

typedef long long ll;

int dp[5][5][38];
int result[5][5];

void init() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);
}

int main() {
    init();
    int N;
    ll B;
    cin >> N >> B;
    // 단위 행렬 I
    for (int i = 0; i < N; i++) result[i][i] = 1;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> dp[i][j][0];
        }
    }
    // 분할 정복
    for (int log = 1; log <= 37; log++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    // 행렬 곱
                    dp[i][j][log] = (dp[i][j][log] + ((dp[i][k][log - 1] % MOD) * (dp[k][j][log - 1] % MOD)) % MOD) % MOD;
                }
            }
        }
    }
    // 이진
    string bin = "";
    while (B) {
        bin += to_string(B % 2);
        B /= 2;
    }

    int log = 0;
    for (char b : bin) {
        int digit = (b - '0');
        int temp[5][5] = {0}; // 행렬곱할 때 숫자 바뀌므로 temp 생성
        if (digit) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    for (int k = 0; k < N; k++) {
                        temp[i][j] = (temp[i][j] + (result[i][k] * dp[k][j][log] % MOD)) % MOD;
                    }
                }
            }
            memcpy(result, temp, sizeof(result));
        }

        log++;
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << result[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

 

0. 아이디어

---

$$A^B = A^{2^{b_1}+2^{b_2}+...+2^{b_n}}$$

 

즉, B=6이면

 

$$ A^6 = A^{2^2+2^1} = A^{2^2}·A^{2^1}$$

 

6을 이진화 하면 110으로 표현이 가능하다.

 

$A^{2^n}$ 표를 DP를 통해 테이블을 만들고 가능한 숫자들의 행렬곱을 만들어주면 된다.

1. 시간복잡도 줄이기

---

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

라는 문구를 보면 B는 지수승인데 수가 커서 시간복잡도가 커질 것이다.

 

또한 분류에 분할정복이 나와있기 때문에 분할정복을 생각할 수있었다.

2. 행렬 곱에 대한 DP를 분할 정복으로 저장 해놓기

---

100,000,000,000는 $2^{37}$이하 이므로 행렬에 대한 채널을 0~37로 해준다

 

여기에 저장되는 정보는 $2^{n}$이 된다.

.3. 이진수 변환

---

    string bin = "";
    while (B) {
        bin += to_string(B % 2);
        B /= 2;
    }

는 이진수로 변환하려면 뒤집기를 해야되지만, 어차피 계산을 첫째 자리 부터 사용해야되기 때문에 바꾸지 않는다.

 

예) 6 : 110 -> 011로 저장되는데 0, 1, 1 순으로 for문을 통해 사용할 거임.

4. 모듈러 성질

---

행렬곱으로인해 숫자가 커지므로 1000이 넘게 나오는 연산부분에 모듈러를 적용시켜준다.

 

5. 그 외

---

① result는 단위 행렬로 초기화를 시켜준다.

 

모든 원소를 1로 초기화 시키는 실수를 하기도 했다.

 

② 분할정복으로 다시 행렬곱을 표현할 때 temp 행렬로 임시로 만들어야한다.

 

result 그대로에다가 곱을하면 result가 계속 업데이트 되니 제대로 된 행렬곱이 이루어지지 않는다.

 

 

*여담: 새벽에 재밌게 풀고 결국 밤새서 잠이라도 깰겸 오랜만에 써보는 백준 풀이, 9시 학교가야한다....