[C++] 10830번 행렬 제곱 - 수학, 분할 정복, 분할 정복을 이용한 거듭제곱, 선형대수학

1. 문제

• 크기가 N*N인 행렬 A가 주어질 때 A의 B제곱을 구하는 프로그램을 작성하시오. 각 원소를 1,000으로 나눈 나머지를 출력한다.

<입력>

• - 1 -   \(N, B(2 \leq N \leq 5, 1 \leq B \leq 100,000,000,000)\)
• - N개의 줄 -   행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수, 또는 0이다.

<출력>

• 행렬 A를 B 제곱한 결과를 출력한다.

2. 재정의

• X

3. 해결 방법

• X

4. 실수한 점, 개선할 점

• 문제 조건, 특히 숫자 범위를 확인하고 long long 범위를 넘어갈 수 있는지 재차 확인하기!

<코드>

#include <iostream>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
typedef long long ll;

const int MAX_N = 6;
const int mod = 1000;

// <문제>
// 행렬의 크기 N, 승수 B
int N;
ll B;
// start, power, matrix
int stma[MAX_N][MAX_N], pma[MAX_N][MAX_N], ma[MAX_N][MAX_N];

void input() {
    cin >> N >> B;
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            cin >> ma[i][j];
            ma[i][j] %= 1000;
            pma[i][j] = ma[i][j];
        }
    }
    
    for(int i=1; i<=N; i++)
        stma[i][i] = 1;
}

// 행렬 곱
void multiple(int ma1[MAX_N][MAX_N], int ma2[MAX_N][MAX_N]) {
    // 행렬 곱 후 값
    int num[MAX_N][MAX_N] = {};
    for(int k=1; k<=N; k++) {
        for(int i=1; i<=N; i++) {
            int x = ma1[i][k];
            
            for(int j=1; j<=N; j++)
                num[i][j] = (num[i][j] + x*ma2[k][j]%mod) % mod;
        }
    }
    
    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++)
            ma1[i][j] = num[i][j];
}

// 분할 정복
void power(ll n) {
    while(n) {
        if(n & 1)
            multiple(stma, pma);
        multiple(pma, pma);
        n >>= 1;
    }
}

int main() {
    fastio;
    
    input();
    
    power(B);
    
    for(int i=1; i<=N; i++, cout << '\n')
        for(int j=1; j<=N; j++)
            cout << stma[i][j] << ' ';
    
    return 0;
}

 

<문제 바로가기>

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

10830번: 행렬 제곱

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.