[백준] 10830번 : 행렬 제곱

문제

 

---

풀이

 

myunji.tistory.com/255

[백준] 1629번 : 곱셈

myunji.tistory.com/257?category=1154147

[백준] 2740번 : 행렬 곱셈

이 두문제를 섞은 문제다.

문제를 분할하는 divide 함수는 그대로 써도 되고 행렬을 곱하는 함수만 추가하면 될 것 같은데 난관이 하나 있었다.

모든 함수의 리턴값이 2차원 배열이어야 한다는 것이었다.

 

처음에는 2차원 배열을 리턴형으로 하는 함수를 작성하고자 포인터도 쓰고 이것저것 썼는데 실패했다.

그러다가 2차원 벡터를 리턴해야겠다는 생각이 들었고, 검색했더니 이게 더 쉬울 것 같았다.

리턴 처리만 해결되면 지금까지 작성해왔던 코드를 재활용해 풀 수 있는 문제였다.

---

소스코드

 

#include <iostream>
#include <vector>

using namespace std;

typedef vector<vector<int>> matrix;
const int DIVISOR = 1000;
matrix inputA;
matrix result;

matrix multiplyMatrix(int N, matrix A, matrix B) {
    matrix res(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++)
                res[i][j] += (A[i][k] * B[k][j]);
            res[i][j] %= DIVISOR;
        }
    }
    return res;
}

matrix divide(int N, long long B) {
    matrix tmp;

    if (B == 1) //더이상 나눌 수 없음
        return inputA;
    else {
        if (B % 2 == 0) { //짝수 거듭제곱일 때
            tmp = divide(N, B / 2);
            return multiplyMatrix(N, tmp, tmp);
        } else //홀수 거듭제곱일 때
            return multiplyMatrix(N, inputA, divide(N, B - 1));
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, input;
    long long B;
    vector<int> tmp;

    cin >> N >> B;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> input;
            tmp.push_back(input);
        }
        inputA.push_back(tmp);
        tmp.clear();
    }

    result = divide(N, B);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << result[i][j] % DIVISOR << ' '; //1000만 들어올 때
        cout << '\n';
    }
}

전체 소스코드다.

 

typedef vector<vector<int>> matrix;
const int DIVISOR = 1000;

먼저 중복될 일이 많을 코드들을 typedef으로 선언하거나 상수화했다.

 

    int N, input;
    long long B;
    vector<int> tmp;

    cin >> N >> B;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> input;
            tmp.push_back(input);
        }
        inputA.push_back(tmp);
        tmp.clear();
    }

2차원 벡터의 입력을 처리하는 부분이다.

먼저 1차원 벡터인 tmp에 한 줄을 입력 받고 tmp를 넣어주는 것이다. 사용한 tmp는 clear 해야 다시 쓸 수 있다.

 

matrix divide(int N, long long B) {
    matrix tmp;

    if (B == 1) //더이상 나눌 수 없음
        return inputA;
    else {
        if (B % 2 == 0) { //짝수 거듭제곱일 때
            tmp = divide(N, B / 2);
            return multiplyMatrix(N, tmp, tmp);
        } else //홀수 거듭제곱일 때
            return multiplyMatrix(N, inputA, divide(N, B - 1));
    }
}

divide 함수이다. 리턴형이 2차원 벡터가 됐고, 곱셈 과정에서 multiplyMatrix 함수를 호출하는 것 이외에는 1629번과 같은 내용이다.

 

matrix multiplyMatrix(int N, matrix A, matrix B) {
    matrix res(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++)
                res[i][j] += (A[i][k] * B[k][j]);
            res[i][j] %= DIVISOR;
        }
    }
    return res;
}

행렬의 곱셈을 하는 multilplyMatrix 함수이다.

matrix res(N, vector<int>(N)) 처럼 미리 NxN의 공간을 확보하면 배열에 값을 추가하는 것처럼 입력을 할 수 있다.

그래서 2차원 배열을 사용했던 2740번의 코드와 거의 유사하게 작성할 수 있다.

 

    result = divide(N, B);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << result[i][j] % DIVISOR << ' '; //1000만 들어올 때
        cout << '\n';
    }

출력할 때 주의해야할 점이 있다. 입력될 수 있는 값 중에서는

 

2 1

1000 1000

1000 1000

 

이 있을 수도 있다.

해당 입력이 divide 함수를 거치면 입력값 그대로 result에 들어갈텐데 모든 값을 1000으로 나눈 나머지를 출력해야 하기 때문에 출력 과정에서 DIVISOR로 나누는 과정을 넣어준다.