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

1. 문제

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

10830번: 행렬 제곱

 

2. 알고리즘 분류

• 수학
• 분할 정복
• 분할 정복을 이용한 거듭제곱
• 선형대수

 

3. 소스 코드

#include <iostream>
using namespace std;

long long N, B;
long long matrix[5][5];
long long ans[5][5];

void input() {
	// N : 행렬의 크기, B :  거듭제곱 횟수
	cin >> N >> B;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> matrix[y][x];
		}
		ans[y][y] = 1;	// 단위행렬 입력
	}
}

// 두 행렬을 곱하는 함수
void multi_matrix(long long matrix1[5][5], long long matrix2[5][5]) {
	long long tmp[5][5];

	// 행렬 곱 계산
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			long long sum = 0;

			for (int i = 0; i < N; i++) {
				sum += matrix1[y][i] * matrix2[i][x];
			}

			tmp[y][x] = sum % 1000;		// 1000으로 나누기
		}
	}

	// 임시행렬 값을 Matrix1에 덮어씌우기
	for (int y = 0; y < N; y++)
		for (int x = 0; x < N; x++)
			matrix1[y][x] = tmp[y][x];
}

void solve() {
	while (B > 0) {
		// 홀수일 경우, ans와 matrix 곱
		if (B % 2 == 1)
			multi_matrix(ans, matrix);

		// matrix 거듭제곱
		multi_matrix(matrix, matrix);
		B /= 2;
	}
}

// 행렬 출력하는 함수
void print_matrix(long long matrix1[5][5]) {
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cout << matrix1[y][x] << " ";
		}
		cout << "\n";
	}
}

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

	input();
	solve();
	print_matrix(ans);

	return 0;
}

 

4.  상세 설명

1. B를 2로 나누면서, 해당 Matrix를 계속 거듭제곱
2. B를 2로 나누었을 때, 나머지가 1이면 ans에 이 때까지 거듭제곱한 Matrix를 곱함
3. B가 0이 될 때까지, 1 ~ 2번 과정을 반복

 

4 - 1) 예제

1. B를 2로 나누면서, 해당 Matrix를 계속 거듭제곱    
2. B를 2로 나누었을 때, 나머지가 1이면 ans에 이 때까지 거듭제곱한 Matrix를 곱함
3. B가 0이 될 때까지, 1 ~ 2번 과정을 반복

ex) B = 5로 가정, 거듭제곱해가는 행렬 M, 처음 입력받은 행렬 Mo

	1차 반복
	B = 5 -> 2 ... 1(나머지)
    => ans = ans * M = Mo
    => M = M * M = Mo * Mo = Mo^2
    
    2차 반복
    B = 2 -> 1 ... 0(나머지)
    => M = M * M = Mo^2 * Mo^2 = Mo^4
    
    3차 반복
    B = 1 -> 0 ... 1(나머지)
    => ans = ans * M = Mo * Mo^4 = Mo^5

5.  문법

5 - 1) 두 행렬을 곱하는 함수

void multi_matrix(long long matrix1[5][5], long long matrix2[5][5]) {
	long long tmp[5][5];

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			long long sum = 0;

			for (int i = 0; i < N; i++) {
				sum += matrix1[y][i] * matrix2[i][x];
			}

			tmp[y][x] = sum
		}
	}

	for (int y = 0; y < N; y++)
		for (int x = 0; x < N; x++)
			matrix1[y][x] = tmp[y][x];
}

 

5 - 2) 분할 정복을 이용한 거듭제곱

void solve() {
	while (B > 0) {
		if (B % 2 == 1)
			multi_matrix(ans, matrix);

		multi_matrix(matrix, matrix);
		B /= 2;
	}
}