10830번

10830번 - 행렬 제곱

행렬의 제곱을 구하는 방법으로, 행렬의 곱셈과 거듭제곱 수를 구하는 방식의 응용이었다.

나는 multi 함수를 통해 행렬의 곱을, calc 함수를 통해 거듭제곱을 분할정복으로 풀었다.

문제에서 배운점

1.

처음에 이차원 배열을 반환해주는 함수를 만들려고 했으나, 생각보다 어렵고 복잡했다.

그래서 구글링을 해보니, 배열을 반환하는 함수는 vector 나 동적할당을 쓰는 걸로 대체하는게 좋다는 것을 알았다.

그래서 vector 를 이용해서 이차원 배열을 반환해주니까 훨씬 편했다.

2.

처음에 vector 를 초기화 하는 방법은 resize 로 했었다. 그러다보니 이 문제를 풀때 vector<vector<int>> v 같은 경우에

v.resize(N) 을 해주고 각 각의 v[i].resize(N) 을 해주는 방식으로 풀었더니, 코드가 지저분했다.

다른 분들 코드를 보니 vector<vector<int>> v(N,vector<int> (N)) 이라는 방식으로 초기화 하는 걸 따라하니 굉장히 쉬웠다.

3.

vector 는 설정을 하지 않고 초기화 하면 값이 0으로 초기화 된다.

4. 질문 vector 인자값 전달할 때 '&' 유무의  차이점

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
long long N, B;
const long long mod = 1000;
vector<vector<long long>> multi(vector<vector<long long>> a, vector<vector<long long>> b)
{
    vector<vector<long long>> ret(N, vector<long long>(N));
 
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            long long sum = 0;
            for (int k = 0; k < N; k++)
            {
                sum += ((a[i][k]%mod)*(b[k][j]%mod))%mod;
            }
            ret[i][j] = sum%mod;
        }
    }
 
    return ret;
}
 
vector<vector<long long>> calc(vector<vector<long long>> a, long long b)
{
    if (b == 0)
    {
        vector<vector<long long>> ret(N,vector<long long> (N));
 
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (i == j)
                {
                    ret[i][j] = 1;
                }
                else
                {
                    ret[i][j] = 0;
                }
            }
        }
 
        return ret;
    }
    else if (b % 2 == 0)
    {
        vector<vector<long long>> ret;
 
        ret = calc(a, b / 2);
 
        return multi(ret, ret);
    }
    else
    {
        vector<vector<long long>> ret;
 
        ret = calc(a, b-1);
 
        return multi(a, ret);
    }
}
 
int main()
{
    
 
    scanf("%lld %lld", &N, &B);
    vector<vector<long long>> A(N, vector<long long>(N));
    
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%lld", &A[i][j]);
        }
    }
    vector<vector<long long>> temp=calc(A, B);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            printf("%lld ", temp[i][j]);
        }
        puts("");
    }
 
    return 0;
}