[백준] 10830 행렬제곱 C++

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

10830번: 행렬 제곱

오랜만에 분할정복 문제이다.

dp를 사용하지 않아서 알고리즘 자체는 어렵지 않는데 c++사용할때 조금 문제가 있었다.

#include <iostream>
#include <stdlib.h>
using namespace std;
void copy(int* dest, const int* origin, int N) {
    // N: size of dest(same as size of origin)
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            *(dest + i * N + j) = *(origin + i * N + j);
        }
    }
};
int* matmul(const int* arr1, const int* arr2, int N) {
    int* ret = (int*)malloc(sizeof(int) * N * N);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            int tmp = 0;
            for (int k = 0; k < N; ++k) {
                tmp += (*(arr1 + i * N + k)) * (*(arr2 + k * N + j));
            }
            *(ret + i * N + j) = (tmp % 1000);
        }
    }
    return ret;
};

int* devideAndConquer(const int* matrix, int N, int num_m) {
    // N: size of matrix, num_m: the number of multiply (num_m times)
    int* new_ret = (int*)malloc(sizeof(int) * N * N);
    if (num_m == 1) {
        copy(new_ret, matrix, N);
        return new_ret;
    }
    if (num_m % 2) { // odd
        new_ret = matmul(matmul(devideAndConquer(matrix, N, num_m / 2), devideAndConquer(matrix, N, num_m / 2), N), matrix, N);
    }
    else { //even
        new_ret = matmul(devideAndConquer(matrix, N, num_m / 2), devideAndConquer(matrix, N, num_m / 2), N);
    }
    return new_ret;
}

int main() {
    // 0. 입력
    // 0-1. 변수 입력
    int N, B, i, j;
    cin >> N >> B;
    // 0-2. 동적할당을 사용해서 n by n matrix 생성
    int* mat = (int*)malloc(sizeof(int) * N * N);
    int* ret = (int*)malloc(sizeof(int) * N * N);
    for (i = 0; i < N; ++i) {
        for (j = 0; j < N; ++j) {
            cin >> *(mat + i * N + j);
        }
    }
    // 1. 분할정복
    ret = devideAndConquer(mat, N, B);
    for (i = 0; i < N; ++i) {
        for (j = 0; j < N; ++j) {
            cout << *(ret + i * N + j) << ' ';
        }
        cout << endl;
    }
    free(mat);
    free(ret);
    return 0;
}

첫번째 시도:

동적할당을 사용해서 이차원 배열처럼 사용했는데 메모리 초과가 떴다.

아마 함수내에서 new_ret을 계속 동적할당 받아서 return 하는데 이후에 동적할당 된 값들을 free로 해제 해야하는데 하지 못해서 생기는 문제같다.

함수 바깥에서 해제하는 방법을 알지 못해서 다른 방법을 사용해야했다.

 

#include <iostream>
#include <vector>
using namespace std;
typedef vector<vector<long long>> matrix;
matrix operator * (const matrix a, const matrix b) {
    long long size = a.size();
    matrix ret(size, vector<long long>(size));
    long long i, j, k;
    for (i = 0; i < size; ++i) {
        for (j = 0; j < size; ++j)
        {
            for (k = 0; k < size; ++k) {
                ret[i][j] += a[i][k] * b[k][j];
            }
            ret[i][j] %= 1000;
        }
    }

    return ret;
}

matrix pow(matrix a, long long N) {
    // N: the number of multiply (num_m times)
    long long size = a.size();
    matrix ret(size, vector<long long>(size));
    if (N == 1) {
        matrix unit(size, vector<long long>(size));
        for (long long i = 0; i < size; i++)
        {
            unit[i][i] = 1;
        }
        ret = a * unit;
        return ret;
    }

    matrix tmp(size, vector<long long>(size));
    tmp = pow(a, N / 2);
    if (N % 2) { // odd
        ret = tmp * tmp * a;
    }
    else { //even
        ret = tmp * tmp;
    }
    return ret;
}

int main() {
    // 0. 입력
    // 0-1. 변수 입력
    long long N, B, i, j;
    cin >> N >> B;
    // 0-2. 동적할당을 사용해서 n by n matrix 생성
    matrix mat(N, vector<long long>(N));
    matrix ret(N, vector<long long>(N));
    for (i = 0; i < N; ++i) {
        for (j = 0; j < N; ++j) {
            cin >> mat[i][j];
        }
    }
    // 1. 분할정복
    ret = pow(mat, B);
    for (i = 0; i < N; ++i) {
        for (j = 0; j < N; ++j) {
            cout << ret[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}

 

두번째 시도:

vector STL을 사용해서 시도하니 메모리 문제는 사라졌다. 

알고리즘상 문제가 없다고 생각했는데 80퍼센트에서 틀렸다.

찾아보니 원소가 1000 이 들어오고 N=1인 경우에 출력하는 값도 1000이 되므로 생기는 문제였다. 

단위 배열을 하나 생성해서 곱해주는 걸로 했더니 쉽게 해결할수 있었다.

---

이 문제는 동적할당을 사용해보려고 했었는데 풀리지 않아서 애를 많이 먹었다.

하지만 STL을 배울수 있던 문제였고, operator 값을 설정할수 있다는 것도 알게 되었다.

C++에서 동적할당에 대해서 조금더 고민을 해봐야할거같고 알고리즘을 위해서 STL도 자주 사용해봐야겠다.