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

예제 입력 1

2 5
1 2
3 4

예제 출력 1

69 558
337 406

예제 입력 2

3 3
1 2 3
4 5 6
7 8 9

예제 출력 2

468 576 684
62 305 548
656 34 412

예제 입력 3

5 10
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1

예제 출력 3

512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512

https://www.acmicpc.net/problem/10830(출처 : 백준 코딩)

 

 어려운 문제는 아니었다. 나는 해당 문제를 이렇게 풀이하였다.

1. 행렬의 곱셈 정의에 따라서 행렬 곱셈을 함수로 구현
2. 행렬 곱셈을 구현한 함수와 분할 정복 알고리즘을 활용하여 거듭 제곱 함수를 구현

사실상 분할 정복 알고리즘을 활용할 수 있냐를 묻는 문제였다. 코드는 다음과 같다.

#include <iostream>
#include <string>
#include <sstream>
#include <math.h>
#include <vector>

int N, B;

std::vector<unsigned long long int> operator*(std::vector<unsigned long long int> v1, std::vector<unsigned long long  int> v2) {
	if (v1.size() != v2.size()) {
		return std::vector<unsigned long long  int>();
	}
	else {
		int n = N;

		std::vector<unsigned long long  int> result(n * n);

		for (int i = 0; i < n; i++) { 
			for (int j = 0; j < n; j++) { 
				for (int k = 0; k < n; k++) {
					result[n * i + j] += v1[n * i + k] * v2[n * k + j];
				}
			}
		}

		return result;
	}
}

std::vector<unsigned long long  int> pow(std::vector<unsigned long long  int> v, int N) {
	if (N == 1) {
		return v;
	}
	else {
		if (N % 2 == 0) {
			std::vector<unsigned long long  int> r = pow(v, N/2);
			return r*r;
		}
		else {
			std::vector<unsigned long long  int> r = pow(v, N / 2);
			return r*r*v;
		}
	}
}

int main() {
	std::cin >>N>>B;
	std::cin.ignore();

	std::vector<unsigned long long int> v;

	std::string str;
	std::stringstream ss;
	for (int i = 0; i < N; i++) {

		std::getline(std::cin, str);
		ss << str;
		str.clear();

		unsigned long long input;
		for (int j = 0; j < N; j++) {
			ss >> input;
			v.push_back(input);
		}

		ss.clear();
	}


	std::vector<unsigned long long  int> result = pow(v, B);

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

	return 0;
}

 솔직히 출력은 올바르게 나왔는데 뭐가 틀렸는지를 모르겠다. 다른 사람들이 푼 것을 봐도 일차원 배열이냐 이차원 배열이나 정도의 차이 밖에 없는데 다가, 예제에 나온 결과도 제대로 나왔다. 혹시 어느 부분에서 틀렸는지 아는 사람이 있으면 댓글로 가르쳐 줬으면 좋겠다.