[Baekjoon, C++] 10830번: 행렬 제곱

도입

백준 단계별 풀기에서 분할정복 일곱 번째 문제이다.

 

백준 10830번 문제, 입력, 출력

---

백준 10830번 입출력 예제 1

---

풀이

1.1. 행렬의 거듭제곱을 어떤식으로 할 것인가! 정사각형 행렬 A를 13번 거듭제곱을 한다고 가정해보자. A의 제곱부터 차례차례 A를 곱하는 방법이 있다. 하지만, 이렇게 하지 않는다. $A^{13}$이 $(A^6)^2*A$ 으로 표시할 수 있고, 여기서  $A^6$을 알고 있다면? 제곱연산을 2번만 하면 된다. 

 

1.2. 지수가 홀수인가, 짝수인가. 홀수라면 $(A^k)*A$ 일 것이고, 짝수라면 $(A^k)^2$ 으로 표현할 수 있다.

 

1.3. 13을 2진법으로 표현해보자. $1101_2$ 이다. MSB로 계산을 한다. (LSB아님) 1일 때는 홀수로 계산하고 0일때는 짝수로 계산. 

 1 - $(A^0)^2*A$ = $A$ 

 1 - $(A^1)^2*A$ = $A^3$

 0 - $(A^3)^2$ = $A^6$

 1 - $(A^6)^2*A$ = $A^{13}$

 

2. 거듭제곱식에 대해 제곱에 대한 함수(곱셈함수)를 만들어서 분할정복을 한다. 위처럼, 홀수와 짝수일 때를 구별하여서, 함수의 매개변수를 다르게 적용시킨다.

---

 

코드

#include<iostream>  

using namespace std;

long long matrix[6][6], result[6][6], matrixTemp[6][6], n, expo;

void func_mul_matrix(long long matrixA[6][6], long long matrixB[6][6])
{
    //행렬의 곱셈
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            matrixTemp[i][j] = 0;
            for (int k = 1; k <= n; k++)
            {
                matrixTemp[i][j] += matrixA[i][k] * matrixB[k][j];
            }
            matrixTemp[i][j] %= 1000;
        }
    //곱셈결과 matrixA에 넣기
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            matrixA[i][j] = matrixTemp[i][j];

}
int main() {
    
    cin >> n >> expo;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> matrix[i][j];

        }
        result[i][i] = 1;
    }

    //연산의 핵심
    while (expo > 0) 
    {
        if (expo % 2 == 1)//지수 홀수
        {
            func_mul_matrix(result, matrix);
        }
        func_mul_matrix(matrix, matrix);
        expo /= 2;
    }

    //결과 출력
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            cout << result[i][j] << ' ';
        cout << '\n';
    }
}

 

---

마무리

 거듭제곱을 어떤식으로 분할정복으로 풀어내는지 그 메커니즘을 알아야한다. 실제 코딩테스트에서 일일히 하나씩 곱해간다고 생각하면 이미 그 문제는 틀린 것이 된다. 보자마자 바로 이렇게 풀 수 있게 리마인드 하면 좋을 듯 하다.