[C++]백준 - 10830번 문제

10830번: 행렬 제곱 (acmicpc.net)

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

 

 

---

 

생각해 볼 점

---

행렬의 제곱을 함수에서 사용하는 것은 c++ 특성상 이차원 배열보다는 이차원 벡터를 사용하는 것이 낫습니다.

왜냐하면, 함수에서 이차원 배열을 반환하려 노력해봤지만, 원하는만큼 깔끔하게 작성되지 않았습니다.

 

차라리 이차원배열을 typedef를 통해서 하나의 타입으로 지정해버리고, 그에 대한 곱셈 연산자를 오버로딩하여 행렬의 곱셈을 계산하기 편하도록 하였습니다.

 

분할정복을 사용하는 solution 함수에서는, 차수 B에 따라서

 

B가 짝수면, solution(B/2)의 제곱을,

B가 홀수면 solution(B - 1) * solution(1)을 반환합니다.

 

여기서 solution(1)은 입력 받은 행렬과 동일합니다.

 

 

코드

---

#include <iostream>
#include <vector>
using namespace std;

typedef vector<vector<int>> matrix;

matrix original;
int N;

//곱셈 연산자 오버로딩
matrix operator * (const matrix &A, const matrix &B) 
{
    matrix ret;
    ret.assign(N, vector<int>(N));
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            for(int k = 0; k < N; k++) ret[i][j] += A[i][k] * B[k][j];
            ret[i][j] = ret[i][j] % 1000;
        }
    }
    return ret;
}

//재귀 함수
matrix solution(long long B)
{
    if(B == 1) return original;
    if(B % 2 == 0)
    {
        matrix temp = solution(B / 2);
        return temp * temp;
    }
    else
    {
        return solution(B - 1) * original;
    }
}

//출력 함수
void print_matrix(matrix M)
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            printf("%d ", M[i][j] % 1000);
        }
        printf("\n");
    }
}

int main() 
{
    long long B;
    cin >> N >> B;
    
    original.assign(N, vector<int>(N));
	for(int i = 0; i < N; i++)
	{
	    for(int j = 0; j < N; j ++)
	    {
	        cin >> original[i][j];
	    }
	}
	print_matrix(solution(B));
	return 0;
}

 

그 외

---