[Algorithm]Baekjoon 10830번 :: 행렬 제곱

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

10830번: 행렬 제곱

 

ector<vector<int>> initMatrix;
vector<vector<int>> identityMatrix;
 
vector<vector<int>> mulMatrix(vector<vector<int>> a, vector<vector<int>> b, int n)
{
    vector<vector<int>> result(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++)
            {
                result[i][j] += a[i][k] * b[k][j];
            }
            
            result[i][j] %= 1000;
        }
    }
 
    return result;
}
 
vector<vector<int>> recur(vector<vector<int>> m, long long b, int n)
{
    if (b == 0) return identityMatrix;
    if (b == 1) return initMatrix;
 
    vector<vector<int>> t = recur(m, b / 2, n);
 
    if (b % 2 == 0) return mulMatrix(t, t, n);
    return mulMatrix(t, mulMatrix(t, initMatrix,n),n);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    long long n, b;
 
    cin >> n >> b;
 
    vector<vector<int>> m(n, vector<int>(n));
    vector<vector<int>> tZeroMatrix(n, vector<int>(n));
    
    for (int i = 0; i < n; i++)
    {
        tZeroMatrix[i][i] = 1;
    }
 
    identityMatrix = tZeroMatrix;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> m[i][j];
        }
    }
 
    initMatrix = m;
    m = recur(m, b, n);
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << m[i][j] % 1000 << ' ';
        }
        cout << endl;
    }
}

행렬의 거듭제곱을 구하는 문제이다. 

거듭제곱의 수가 굉장히 크기 때문에 분할해서 풀어야하는 문제이다.

정수 n의 거듭제곱을 풀어봤다면 풀 수 있는 문제.

 

마찬가지로 거듭제곱을 2씩 쪼개면서 분할한다. 쪼개다가 b가 0이면 항등행렬을 리턴하고 (정수의 거듭제곱이면 항등원인 1을 리턴), b가 1이면 맨처음 입력받았던 행렬을 리턴한다.

 

행렬의 곱을 수행하는 함수를 따로 작성해줘야 한다는것을 제외하고는 정수의 거듭제곱과 거의 동일하다.

그리고 출력할때도 혹시 모를 테스트케이스를 방지하기 위해 한번더 1000으로 나머지연산을 해준다.

만약 코드를 제출했는데 80%쯤에서 실패가 뜬다면, 아래와같은 테스트케이스를 적용해보길 권장한다.

 

2 1

1000 1000

1000 1000