백준 10830번 : 행렬 제곱 / C++

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

10830번: 행렬 제곱

분할 정복 문제로 거듭제곱을 응용한 문제였다. 행렬의 곱셈 함수는 만들어서 곱한 행렬 포인터를 반환한다.   오늘도 문제를 잘 읽지않고 풀다가 B가 int로 자료형으로 받지못하는 문제였고 1을 제곱할때 1000은 입력받으면 나머지 연산을 해줘야하는데 안해줬다가 틀렸다. 문제를 잘 읽고 해결하는 습관을 가져야겠다.

#include <iostream>
#include <vector>
typedef long long ll;
 
using namespace std;
int N;
ll B;
ll *Arr1;
ll* Arr2;
 
ll* MatrixMultiple(const ll* A, int A_Row, int A_Col, const ll* B, int B_Row, int B_Col)
{
    ll* C = new ll[A_Row * B_Col];
    for(int row =0; row< A_Row; ++row)
        for (int col = 0; col < B_Col; ++col)
        {
            C[row * B_Col + col] = 0;
            for (int i = 0; i < A_Col; ++i)
            {
                C[row * B_Col + col] += (A[row * A_Col + i] * B[i * B_Col + col]) %1000;
            }
            C[row * B_Col + col] = C[row * B_Col + col] % 1000;
        }
 
    return C;
}
 
int main()
{
    cin.tie(NULL);
    std::cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> N >> B;
    Arr1 = new ll[N * N];
    for (int i = 0; i < N * N; ++i)
    {
        ll num;
        cin >> num;
        Arr1[i] = num%1000;
    }
 
    while (B > 0)
    {
        if (B & 1 && Arr2 != nullptr)
            Arr2 = MatrixMultiple(Arr2, N, N, Arr1, N, N);
        else if (B & 1 && Arr2 == nullptr)
            Arr2 = Arr1;
        Arr1 = MatrixMultiple(Arr1, N, N, Arr1, N, N);
        B >>= 1;
    }
 
    for (int row = 0; row < N; ++row)
    {
        for (int col = 0; col < N; ++col)\
        {
            cout << Arr2[row * N + col] << ' ';
        }
        cout << '\n';
    }
 
    return 0;
}