🎲문제

---

주소:백준 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이다.

✅ 풀이

---

풀이방법

행렬 곱셈식을 알고 있다면 어렵지 않게 풀 수 있다. 하지만 제곱수가 integer를 초과하므로 효율적으로 제곱을 계산하는 방법을 사용해야 한다. 2^8 = 4^4 = 8^2 과 같이 제곱수가 짝수일 때 절반으로 줄이는 방법을 이용한다면 빠르게 계산할 수 있다.

1. 초기 입력값이 N과 B를 입력받고 기본 행렬을 입력받는다. 출력할 정답 행렬에는 단위행렬로 초기화한다.

void init() {

	cin >> N >> B;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> procession[i][j];
			answer[i][i] = 1;
		}
	}
}

1. 제곱수를 효과적으로 줄이기위해 제곱수가 짝수라면, 제곱할 대상 행렬을 제곱하여(ex. 2^8 → 4^4) 곱하고 홀수라면 정답 행렬에다 제곱할 대상 행렬을 곱한다.

void solve() {

	while (B > 0) {

		if (B % 2 == 1) {
			multiple_procession(answer, procession);
			B--;
		}
		B /= 2;

		multiple_procession(procession,procession);
	}
}

3.제곱과정은 임시 행렬을 두고 행렬 요소가 모두 계산된다면 %1000을 통해 나머지를 저장한다. 이후 행렬이 모두 곱해진다면, 기존 행렬에 임시행렬을 저장한다.

void multiple_procession(long long x[5][5], long long y[5][5]) {
	long long tmp[5][5];
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			long long multi = 0;
			for (int k = 0; k < N; k++) {
				multi += x[i][k] * y[k][j];
			}
			tmp[i][j] = multi % 1000;
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			x[i][j] = tmp[i][j];
		}
	}

	return;
}

전체 코드

---

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long N, B;
long long procession[5][5];
long long answer[5][5];

void init();
void solve();
void multiple_procession(long long [5][5], long long [5][5]);
void print_procession(long long [5][5]);

void init() {

	cin >> N >> B;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> procession[i][j];
			answer[i][i] = 1;
		}
	}
}
void solve() {

	while (B > 0) {

		if (B % 2 == 1) {
			multiple_procession(answer, procession);
			B--;
		}
		B /= 2;

		multiple_procession(procession,procession);
	}
}

void multiple_procession(long long x[5][5], long long y[5][5]) {
	long long tmp[5][5];
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			long long multi = 0;
			for (int k = 0; k < N; k++) {
				multi += x[i][k] * y[k][j];
			}
			tmp[i][j] = multi % 1000;
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			x[i][j] = tmp[i][j];
		}
	}

	return;
}

void print_procession(long long tmp[5][5]) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << tmp[i][j] << " ";
		}
		cout << "\n";
	}
}

int main() {
	
	init();
	solve();
	print_procession(answer);
	return 0;
}