[C/C++] 백준 10830번 - 행렬 제곱

문제

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

입력

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

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

long long N, B;
long long A[5][5];
long long temp[5][5];
long long ans[5][5];


// 배열 출력
void print_arr(long long arr[5][5])
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			cout << arr[i][j] << " ";
		cout << endl;
	}
}

// 행렬 곱셈
void Matrix_multi(long long X[5][5], long long Y[5][5])
{

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
		{
			temp[i][j] = 0; // 행렬 초기화
			for (int k = 0; k < N; k++)
				temp[i][j] += (X[i][k] * Y[k][j]);

			temp[i][j] %= 1000;
		}

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			X[i][j] = temp[i][j];
}

int main()
{
	cin >> N >> B;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			cin >> A[i][j];
		ans[i][i] = 1; // 정답행렬은 단위행렬로
	}

	while (B > 0)
	{
		if (B % 2 == 1)
		{
			Matrix_multi(ans, A); // 정답행렬에 A행렬 곱하기
		}
		Matrix_multi(A, A);
		B /= 2;
	}

	print_arr(ans); // A를 B번 곱한 결과

}

 

 

 

풀이방법

// 행렬 곱셈
void Matrix_multi(long long X[5][5], long long Y[5][5])
{

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
		{
			temp[i][j] = 0; // 행렬 초기화
			for (int k = 0; k < N; k++)
				temp[i][j] += (X[i][k] * Y[k][j]);

			temp[i][j] %= 1000;
		}

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			X[i][j] = temp[i][j];
}

Matrix_multi()함수에는 배열의 주소값이 파라미터로 들어가게 됩니다. 

 

while (B > 0)
	{
		if (B % 2 == 1)
		{
			Matrix_multi(ans, A); // 정답행렬에 A행렬 곱하기
		}
		Matrix_multi(A, A);
		B /= 2;
	}

그리고 B가 0보다 클때 B가 홀수라면 ans에 A를 곱해주고 A = A*A 로 다시 설정한 뒤 B / 2를 해줍니다.

 

예를들어 B가 5일때

1. B는 홀수이므로 ans = ans * A = A
2. 그리고 A = A^2
3. B = 5/2 = 2 한 후 다시 루프의 위로 이동.
4. B는 짝수이므로 A = A^2 * A^2
5. B = 2/1 = 1 한 후 다시 루프의 위로 이동.
6. B는 홀수이므로 ans = ans * A = A * (A^4) = A^5
7. B = 1/2 = 0 이므로 루프 탈출

 

따라서 ans = A^5 이며 O(N)이아닌 O(logN)의 시간 복잡도에 정답을 구할 수 있게 됩니다.

 

 

 

www.acmicpc.net/problem/10830

10830번: 행렬 제곱