백준 10830 - 행렬 제곱(C++)

문제

크기가 N•N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하는 것이다.

 

입력

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

 

그 다음줄 부터 N개의 줄에 행렬의 각 원소가 주어진다.

 

예제 입력

2 5
1 2
3 4

 

예제 출력

69 558
337 406

 

문제 해결

어디서 힌트를 얻을 수 있을까?

 

'제곱'이라는 키워드에 중점을 둬서 이 문제를 풀어야 한다.

 

거듭 제곱 문제를 풀 때 제곱의 수를 반으로 줄여서 곱하는 것은 똑같은 결과를 가져다 주는 것을 알 수 있다.

 

N^B = N^(B/2) * N^(B/2)

 

이렇게 계속 반으로 줄이다 보면 더 이상 줄이지 못하는 기저 사례가 나오게 되고 처리해 주면 된다.

 

만약 홀수가 나오게 된다면 다음과 같이 처리해주면 된다.

 

N^B = N^(B - 1) * N;

 

코드

#include <iostream>
#include <cstring>

struct SquareMatrix {
	int N;
	long long arr[6][6];
	SquareMatrix operator*(SquareMatrix& other)
	{
		SquareMatrix ret;
		ret.N = this->N;
		std::memset(ret.arr, 0, sizeof(ret.arr));
		for (int i = 0; i < ret.N; i++)	
		{
			for (int j = 0; j < ret.N; j++)
			{
				for (int k = 0; k < ret.N; k++)
					ret.arr[i][j] += ((this->arr[i][k] % 1000) * (other.arr[k][j] % 1000)) % 1000;
				ret.arr[i][j] %= 1000;
			}
		}
		return ret;
	}
};

SquareMatrix identity(int size)
{
	SquareMatrix ret;

	ret.N = size;
	std::memset(ret.arr, 0, sizeof(ret.arr));
	for (int i = 0; i < size; i++)
		ret.arr[i][i] = 1;
	return ret;
}

SquareMatrix power(SquareMatrix& A, long long B)
{
	if (B == 0) return identity(A.N);
	if (B % 2 != 0) return power(A, B - 1) * A;
	SquareMatrix half = power(A, B / 2);
	return half * half;
}

int main(void)
{
	SquareMatrix A;
	long long B;
	std::cin >> A.N >> B;
	for (int i = 0; i < A.N; i++)
	{
		for (int j = 0; j < A.N; j++)
			std::cin >> A.arr[i][j];
	}
	SquareMatrix ret = power(A, B);
	for (int i = 0; i < ret.N; i++)
	{
		for (int j = 0; j < ret.N; j++)
			std::cout << ret.arr[i][j] << " ";
		std::cout << "\n";
	}
	return 0;
}

 

문제 출처

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

10830번: 행렬 제곱