[백준] 10830번 - 행렬 제곱 [Java][C++]

문제 링크

---

1. 문제 풀이

행렬의 거듭제곱을 구하는 문제로 $B$ 의 크기가 최대 $100,000,000,000$ 이어서 단순한 행렬 곱셈의 반복으로는 해결할 수 없다. 행렬의 곱셈은 결합법칙이 성립한다는 점에서 이진 거듭제곱을 적용하면 해결할 수 있다.

최종 결과 행렬의 각 원소를 $1,000$ 으로 나눈 나머지를 출력해야 하는데 나머지 연산은 곱셈과 덧셈에 대한 분배 법칙이 성립해서 행렬 곱셈 과정에서 나머지 연산을 적용해주었다. 초기 행렬의 원소들도 최대 $1,000$ 이하의 자연수여서 행렬 곱셈이 일어나지 않아도 나머지 연산을 적용해야 함에 유의해야 한다.

---

2. 코드

1. 분할 정복을 이용한 거듭제곱 [Java]

반복문을 활용해 구현했다.

import java.io.*;
import java.util.*;

public class Main {

    static final int MOD = 1_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        long B = Long.parseLong(st.nextToken());

        int[][] mat = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                mat[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] result = binPow(mat, B);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sb.append(result[i][j]).append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }

    static int[][] binPow(int[][] mat, long n) {
        int len = mat.length;
        int[][] res = identity(len);

        while (n > 0) {
            if ((n & 1) > 0) res = multiply(res, mat);
            mat = multiply(mat, mat);
            n >>= 1;
        }

        return res;
    }

    static int[][] identity(int len) {
        int[][] id = new int[len][len];
        for (int i = 0; i < len; i++) {
            id[i][i] = 1;
        }
        return id;
    }

    static int[][] multiply(int[][] mat1, int[][] mat2) {
        int len = mat1.length;
        int[][] res = new int[len][len];

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                for (int k = 0; k < len; k++) {
                    res[i][j] += mat1[i][k] * mat2[k][j];
                }
                res[i][j] %= MOD;
            }
        }

        return res;
    }
}

2. 분할 정복을 이용한 거듭제곱 [Java]

재귀를 활용해 구현했다.

import java.io.*;
import java.util.*;

public class Main {

    static final int MOD = 1_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        long B = Long.parseLong(st.nextToken());

        int[][] mat = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                mat[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] result = binPow(mat, B);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sb.append(result[i][j]).append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }

    static int[][] binPow(int[][] mat, long n) {
        if (n == 0) return identity(mat.length);

        int[][] half = binPow(mat, n / 2);
        if (n % 2 == 1) {
            return multiply(multiply(half, half), mat);
        } else {
            return multiply(half, half);
        }
    }

    static int[][] identity(int len) {
        int[][] id = new int[len][len];
        for (int i = 0; i < len; i++) {
            id[i][i] = 1;
        }
        return id;
    }

    static int[][] multiply(int[][] mat1, int[][] mat2) {
        int len = mat1.length;
        int[][] res = new int[len][len];

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                for (int k = 0; k < len; k++) {
                    res[i][j] += mat1[i][k] * mat2[k][j];
                }
                res[i][j] %= MOD;
            }
        }

        return res;
    }
}

3. 분할 정복을 이용한 거듭제곱 [C++]

반복문을 활용해 구현했다.

#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 1000;

using Matrix = vector<vector<int>>;

Matrix identity(int len) {
    Matrix id(len, vector<int>(len));
    for (int i = 0; i < len; i++) {
        id[i][i] = 1;
    }
    return id;
}

Matrix multiply(const Matrix& a, const Matrix& b) {
    int len = a.size();
    Matrix res(len, vector<int>(len));

    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            for (int k = 0; k < len; k++) {
                res[i][j] += a[i][k] * b[k][j];
            }
            res[i][j] %= MOD;
        }
    }

    return res;
}

Matrix binpow(Matrix mat, long long n) {
    int len = mat.size();
    Matrix res = identity(len);

    while (n > 0) {
        if (n & 1) res = multiply(res, mat);
        mat = multiply(mat, mat);
        n >>= 1;
    }

    return res;
}

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

    int n;
    long long b;
    cin >> n >> b;

    Matrix mat(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int x;
            cin >> x;

            mat[i][j] = x;
        }
    }

    Matrix res = binpow(mat, b);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << res[i][j] << ' ';
        }
        cout << '\n';
    }
}

4. 분할 정복을 이용한 거듭제곱 [C++]

재귀를 활용해 구현했다.

#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 1000;

using Matrix = vector<vector<int>>;

Matrix identity(int len) {
    Matrix id(len, vector<int>(len));
    for (int i = 0; i < len; i++) {
        id[i][i] = 1;
    }
    return id;
}

Matrix multiply(const Matrix& a, const Matrix& b) {
    int len = a.size();
    Matrix res(len, vector<int>(len));

    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            for (int k = 0; k < len; k++) {
                res[i][j] += a[i][k] * b[k][j];
            }
            res[i][j] %= MOD;
        }
    }

    return res;
}

Matrix binpow(Matrix mat, long long n) {
    if (n == 0) return identity(mat.size());

    Matrix half = binpow(mat, n / 2);
    if (n % 2) {
        return multiply(multiply(half, half), mat);
    } else {
        return multiply(half, half);
    }
}

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

    int n;
    long long b;
    cin >> n >> b;

    Matrix mat(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int x;
            cin >> x;

            mat[i][j] = x;
        }
    }

    Matrix res = binpow(mat, b);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << res[i][j] << ' ';
        }
        cout << '\n';
    }
}

---

3. 풀이 정보

1. 분할 정복을 이용한 거듭제곱 [Java]

언어	시간	메모리	코드 길이
Java 11	104 ms	14356 KB	1886 B

2. 분할 정복을 이용한 거듭제곱 [Java]

언어	시간	메모리	코드 길이
Java 11	100 ms	14244 KB	1880 B

3. 분할 정복을 이용한 거듭제곱 [C++]

언어	시간	메모리	코드 길이
C++ 17	0 ms	2024 KB	1357 B

4. 분할 정복을 이용한 거듭제곱 [C++]

언어	시간	메모리	코드 길이
C++ 17	0 ms	2156 KB	1368 B

---