[백준][C++] 10830번: 행렬 제곱 <202>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

10830번: 행렬 제곱

생각의 흐름

이런 N승 문제는 기본적으로 진짜로 N승 해버리면 대부분 못푼다.

지금 까지 내가푼 대부분의  N승 문제의 결론은 O(logN) 안에 해결되도록 코드를 구서해야된다는 점 이다.

 

예를 들어 A의 6승을 구해야 한다면 A를 진짜 6번 곱하는 것 이 아니라, A의 3승을 2번 곱하면 된다.

=> (A*A*A) * (A*A*A) 와 같이 A 3승을 2번 곱해야 한다.

위 식을 얼핏 보기에는 A를 6번 곱하는 A*A*A*A*A*A 와 별반 다른점이 없는것 같다. 괄호 말고는 뭐가 달라보이지 않는다!

 

여기서 명심할 점이! (A*A*A) * (A*A*A) 에서 첫 앞덩이인 (A*A*A)를 계산하는 순간 뒷 덩이 까지 계산한 것 이다.

(A*A*A) 를 B라 칭하면 바로 B*B로 바뀌어 버리는 것 이다.

이런식으로 절반만 구하면 나머지도 구하게 되니 시간 복잡도는 O(lonN)안에 가능해진다. 분할정복!!

 

마지막으로 N승에서 N이 짝수일 때와 홀수일때가 조금 다른데, 2^5를 구하는걸 예로 살펴보자!

n = 5, res = 1

 

2^5 = 2 * 2^4  (n이 홀수일 때 밑을 하나 꺼내서 n을 짝수로 만든다) -> n = 4

res = res * 2; (꺼낸 수를 결과값에 저장한다) res = 2

 

2^4 = (2^2)^2 = 4^2 (n이 짝수일 때 밑을 제곱하고 n을 2로 나눈다) -> n = 2

 

4^2 = 16^1 (n이 짝수일때 밑을 제곱하고 n을 2로 나눈다) -> n = 1

 

16^1 = 16 * 16^0 = 16 (n이 홀수일 때 밑을 하나 꺼내서 n을 짝수로 만든다) -> n = 0

res = res * 16; (꺼낸 수를 결과값에 저장한다) res = 32

 

n == 0이면 종료

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000

int N;
long long B;
typedef vector<vector<int>> matrix;

matrix operator*(matrix &a, matrix &b) {
    matrix temp(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++) {
                temp[i][j] += a[i][k] * b[k][j];
            }
            temp[i][j] %= MOD;
        }
    }
    return temp;
}

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

    cin >> N >> B;

    matrix res(N, vector<int>(N));
    matrix mat(N, vector<int>(N));
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> mat[i][j];
        }
        res[i][i] = 1;
    }

    while(B > 0) {
        if(B % 2 == 1) {
            res = res * mat;
        }
        mat = mat * mat;
        B /= 2;
    }

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

    return 0;
}