[Baekjoon] 10830번: 행렬 제곱

 

 

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

10830번: 행렬 제곱

 

---

 

문제 해결 과정

착안

문제에서 행렬을 곱하는 횟수 $B$가 매우 커서 단순하게 행렬 하나씩 곱하며 계산하면 제한 시간 내에 문제를 해결할 수 없으므로, 자기 자신 행렬을 제곱할 때마다 지수가 2의 거듭제곱으로 증가하는 것을 활용하고자 하였다.

 

구현

우선 임의의 $n \times n \space (1 \le n \le 5) $ 크기의 정사각행렬 $M_1, M_2$를 곱하여 결과를 도출하는 함수를 구현하고 테스트한 다음, 재귀적으로 행렬 곱셈을 계산하여 문제를 해결하고자 하였다. 이때, $B$의 값이 1이 될 때까지 절반씩 줄여나가는 방법으로 단순하게 재귀 함수 호출을 구현했을 때는 행렬 $A$를 $B$번 반복하여 곱하는 것과 연산량 차이가 없어 시간 초과가 발생하였다.

 

따라서 행렬을 제곱할 때마다 지수가 2의 거듭제곱으로 늘어나는 것을 이용하기 위해 (즉, $(A^k)^2 = A^{2k}$), 행렬을 곱하는 횟수인 $B$에 대해, 아래와 같이 $B$의 값을 1로 만드는 재귀적 연산 과정을 스택(stack) 자료 구조에 저장하였다.

• $B$가 홀수인 경우: 홀수인 경우를 표현하는 값을 스택에 저장하고, $B$의 값보다 1 작은 값을 다시 $B$에 저장한다.
• $B$가 짝수인 경우: 짝수인 경우를 표현하는 값을 스택에 저장하고, $B$의 값을 2로 나누어 다시 $B$에 저장한다.

 

위의 과정을 통해 스택에 저장된 연산을 하나씩 인출하며, 단위행렬(identity matrix)부터 시작하여 현재까지 계산된 행렬을 제곱하거나, 행렬 $A$를 1회 곱하는 연산을 수행하여 최종적으로 $A^B$의 각 요소들의 값을 구할 수 있다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <stack>

using namespace std;

int Matrix[5][5];
int Answer[5][5];

void Multiply(int size, int inMatrix1[5][5], int inMatrix2[5][5], int outMatrix[5][5])
{
	int temp[5][5] = { 0, };
	for (int i = 0; i < size; i++)
		for (int j = 0; j < size; j++)
			for (int k = 0; k < size; k++)
				temp[i][j] += inMatrix1[i][k] * inMatrix2[k][j];

	for (int i = 0; i < size; i++)
		for (int j = 0; j < size; j++)
			outMatrix[i][j] = temp[i][j] % 1000;
}

void Power(int size, unsigned long long exp)
{
	stack<int> operation;
	while (exp > 0)
	{
		if (exp % 2)
		{
			operation.push(1);
			exp -= 1;
		}
		else
		{
			operation.push(2);
			exp /= 2;
		}
	}

	while (!operation.empty())
	{
		int op = operation.top();
		operation.pop();

		if (op == 1)
			Multiply(size, Answer, Matrix, Answer);
		else
			Multiply(size, Answer, Answer, Answer);
	}
}

int main()
{
	int N;
	unsigned long long B;
	cin >> N >> B;
	
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> Matrix[i][j];
	
	for (int i = 0; i < N; i++)
		Answer[i][i] = 1;
	
	Power(N, B);
	
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			cout << Answer[i][j] << " ";
		cout << "\n";
	}

	return 0;
}

 

실행 결과