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

문제

• 10830번 : 행렬 제곱
• Rank : Gold IV
• 링크 : https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱

 

풀이 전략

• A^n = A^(n/2) * A^(n/2) 인 점을 이용하여, 분할 정복한다.
• 분할 정복으로 곱셈 문제를 해결할 경우 중복된 계산이 많이 발생하므로, 제곱 계산의 결과를 메모이제이션하여 중복된 계산을 생략한다.
• 이 때, N이 최대 100,000,000,000이고 분할당 1/2으로 감소하므로, Array 대신 Map을 사용하여 결과를 저장하도록 한다.

전체 소스 코드

//Backjoon Problem No.10830
//https://www.acmicpc.net/problem/10830
//Mist16, 2022-02-05
#include <iostream>
#include <map>

using namespace std;

unsigned int N = 0;
unsigned long long B = 0;

struct matrix
{
	unsigned int mat[5][5];

	matrix()
	{
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 5; j++)
				mat[i][j] = 0;
	}
};

map<unsigned long long, matrix> dices;

matrix matrixMulti(const matrix& a, const matrix& b)
{
	matrix temp;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			unsigned int tempv = 0;
			for (int k = 0; k < N; k++)
			{
				tempv = tempv + (a.mat[i][k] * b.mat[k][j]);
			}
			tempv = tempv % 1000;
			temp.mat[i][j] = tempv;

		}
	}
	return temp;
}

matrix getNSquare(unsigned long long n)
{
	auto iter = dices.find(n);

	if (iter == dices.end())
	{
		unsigned long long a, b;
		a = n / 2;
		b = n - a;
		matrix tempmat;
		tempmat = matrixMulti(getNSquare(a), getNSquare(b));
		dices.insert(pair <unsigned long long, matrix>(n, tempmat));
		return tempmat;

	}
	return iter->second;
}

void run()
{
	matrix result = getNSquare(B);
	
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cout << result.mat[i][j] % 1000 << " ";
		}
		cout << endl;
	}
	return;
}

int main()
{
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	matrix temp;
	
	cin >> N >> B;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> temp.mat[i][j];
		}
	}

	dices.clear();
	dices.insert(pair <unsigned long long, matrix>(1, temp));

	run();

	return 0;
}

풀이 중 주의 사항

• N의 범위가 0 ~ 100,000,000,000이므로, 충분히 큰 변수 형태를 사용하여 저장한다.
• 행렬의 구성요소가 1000으로 입력되고, 제곱연산을 하지 않을 경우에도 0으로 출력해야 하는 점을 주의하도록 한다.