백준10830번 - 행렬 제곱 자바스크립트(Node.js)풀이

문제

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

 

입력

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤  5, 1 ≤ B ≤ 100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

 

 

 

문제유형

수학

분할 정복

분할 정복을 이용한 거듭제곱

선형대수학

 

---

 

행렬을 n제곱시키는 (개념적으로는)간단한문제.

하지만 시간 제한(1초)에 비해 B값이 커서 최적화를 시켜야 한다.

 

보통 행렬의 제곱을 최적화하는 연산은 행렬의 대각화로 처리한다고 배웠지만,

모든 행렬이 대각화가 가능한 것이 아니고, PS에서는 최악의 경우가 중요하므로

대각화가 가능한지 확인하지 않고 바로 제곱연산 자체를 최적화 해야한다.

 

제곱연산을 최적화하는 부분은 a^2n = a^n * a^n 이라는 간단한 성질을 이용하여 처리하였다.

홀수인 경우에는 a를 한번 미리 연산해줘서 앞으로 제곱해야할 n의 값을 짝수로 변환하였다.

 

 

전체 코드

const fs = require('fs');
const stdin = (process.platform === 'linux'
        ? fs.readFileSync('/dev/stdin').toString()
        : `2 5
1 2
3 4`
).split('\n');

const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();

function mulMat(mata, matb){
    // tmpmat init
    let tmpmat = new Array(size);
    for(let i=0; i<size; i++){
        tmpmat[i] = new Array(size);
    }
    for(let i=0; i<size; i++){
        for(let j=0; j<size; j++){
            tmpmat[i][j] = 0;
        }
    }

    // mul
    for(let i=0; i<size; i++){
        for(let j=0; j<size; j++){
            for(let k=0; k<size; k++){
                tmpmat[i][j] += mata[i][k] * matb[k][j];
            }
            tmpmat[i][j] %= 1000;
        }
    }

    return tmpmat;
}

// init
const f = input().split(' ').map(Number);
const size = f[0];
let pow = f[1];
let matrix = [];

for(let i=0; i<size; i++){
    matrix.push(input().split(' ').map(Number)); //deep copy
}

// unit matrix
let tmpmat = new Array(size);
for(let i=0; i<size; i++){
    tmpmat[i] = new Array(size);
}
for(let i=0; i<size; i++){
    for(let j=0; j<size; j++){
        tmpmat[i][j] = 0;
    }
    tmpmat[i][i] = 1;
}

while(pow){
    if(pow % 2 == 1){
        tmpmat = mulMat(tmpmat, matrix);
        pow--;
    }
    pow /= 2;
    matrix = mulMat(matrix, matrix);
}

// answer
for(let i=0; i<size; i++){
    let tmp = "";
    for(let j=0; j<size; j++){
        tmp += tmpmat[i][j] + " ";
    }
    console.log(tmp);
}

 

10830번: 행렬 제곱