[Baekjoon/백준] 10830번: 행렬 제곱(C/C++)

단계별로 풀어보기 20단계(분할 정복) 7번 문제

https://www.acmicpc.net/step/20

분할 정복 단계

---

백준 10830번: 행렬 제곱

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

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제곱한 결과를 출력한다.

---

접근 방법

이번 문제는 N과 B를 입력받고, N*N 크기의 행렬 A를 입력받는다. 그뒤 이 A^B를 구한 뒤 원소를 1000으로 나눈 나머지를 출력하는 문제다.

일단 N 값 자체는 최대 5로 그리 크지 않다. 문제는 B가 매우 큰 값을 가지고, A^B를 구해서 1000으로 나눈 나머지를 구해서 출력해야하기때문에 B를 분할 정복으로 처리해서 값을 구해야한다.

B를 분할정복하는 것은 B가 짝수일 때와 홀수일 때를 구분해서 문제를 풀면된다. B가 홀수라면 A * A^(B - 1)로 계산하고, 짝수라면 (A^2)^(B / 2)를 해서 B를 절반으로 나눠 계산할 수 있다. 이를 활용해서 반복문 함수를 만들고, B = 0이 될때까지 계속해서 반복한다면 문제를 해결할 수 있을 것이다.

---

코드

#include <iostream>
using namespace std;

int N;
long long B, A[5][5], result[5][5];

void pow(long long arr1[5][5], long long arr2[5][5]) {
	long long temp[5][5];

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) {
			temp[i][j] = 0;
			for (int h = 0; h < N; h++)
				temp[i][j] += (arr1[i][h] * arr2[h][j]);

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

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

int main(int argc, char *argv[]) {
	cin >> N >> B;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			cin >> A[i][j];
		result[i][i] = 1;
	}
	
	while (B > 0) {
		if (B % 2 == 1)
			pow(result, A);
		pow(A, A);
		B /= 2;
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			cout << result[i][j] << " ";
		cout << endl;
	}

	return 0;
}

---

결과

백준 제출 결과