백준 10830번 [행렬 제곱](C++)-yes6686- 티스토리

백준 문제 풀이: 10830 [행렬 제곱]

---

문제 링크: https://www.acmicpc.net/problem/10830

문제 설명:

N×N 정수 행렬 A가 주어질 때, A^B를 구하고, 그 결과의 각 원소를 1,000으로 나눈 나머지를 출력하는 문제입니다.

입력:

• 첫째 줄에 행렬 크기 N (2 ≤ N ≤ 5)과 거듭제곱 횟수 B (1 ≤ B ≤ 100,000,000)이 주어집니다.
• 둘째 줄부터 N개의 줄에 걸쳐 행렬의 원소가 주어집니다. 행렬의 각 원소는 1,000보다 작은 자연수입니다.

출력:

• A^B의 결과를 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <cstring>
using namespace std;

int n;
long long b;
int arr[6][6];
int result[6][6];

// 행렬 곱셈 함수
void matrixMultiply(int a1[6][6], int a2[6][6]) {
    int temp[6][6] = {0};

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                temp[i][j] += a1[i][k] * a2[k][j];
                temp[i][j] %= 1000;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            a1[i][j] = temp[i][j];
        }
    }
}

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

    cin >> n >> b;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
        result[i][i] = 1; // 단위 행렬 초기화
    }

    while (b > 0) {
        if (b % 2 == 1) {
            matrixMultiply(result, arr); // b가 홀수일 때 현재 행렬 곱셈
        }
        matrixMultiply(arr, arr); // 행렬 제곱
        b /= 2;
    }

    // 결과 출력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << result[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

예제

입력:
2 5
1 2
3 4

출력:
69 558
337 406

입력:
3 3
1 2 3
4 5 6
7 8 9

출력:
468 576 684
62 89 116
656 602 548

---

코드 설명

• 행렬 곱셈: matrixMultiply 함수는 두 행렬을 곱한 결과를 모듈로 연산을 통해 구합니다.
• 이진 거듭제곱:
  • 거듭제곱 횟수를 반으로 줄이는 방식으로 행렬 곱셈 연산 횟수를 줄입니다.
  • b % 2 == 1일 때 현재 행렬을 결과 행렬에 곱합니다.
• 단위 행렬 초기화: 결과 행렬 result는 초기에 단위 행렬로 설정됩니다.

시간 복잡도

• 행렬 곱셈의 시간 복잡도는 O(N³)입니다.
• 이진 거듭제곱의 시간 복잡도는 O(log B)입니다.
• 전체 시간 복잡도는 O(N³ × log B)로 제한된 범위 내에서 효율적입니다.

---

결과

코드는 입력된 행렬의 거듭제곱을 효율적으로 계산하며, 모듈로 연산을 통해 메모리 초과와 연산 시간을 최소화합니다. 이진 거듭제곱을 활용해 문제를 효과적으로 해결합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!