[BOJ / Node.js] 10830 행렬 제곱

10830번: 행렬 제곱

 

문제

크기가 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제곱한 결과를 출력한다.

예제 입력 

2 5
1 2
3 4

예제 출력 

69 558
337 406

 

Solve

• 행렬을 곱하는 함수 matrixTimes를 만들어 주었습니다.
• 제곱수의 범위가 100,000,000,000까지 주어질 수 있어 단순 반복으로는 해결할 수 없습니다. 따라서, 제곱의 특성을 이용하여 count를 2로 나누어 주면서 count가 짝수일 경우에는 제곱된 행렬을 서로 곱해주고, 홀수일 경우 반환될 행렬에 값을 저장하여 탐색을 O(logN)만큼 줄여줄 수 있었습니다.

Code

const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");

const [n, b] = input.shift().split(' ').map(el=>+el);
const arr = input.map(el=>el.split(' ').map(el=>(+el)%1000));

const matrixTimes = (matrix1, matrix2, n) => {
    const newMatrix = Array.from({length:n},()=>Array.from({length:n},()=>0));
    for(let y = 0; y < n; y++) {
        for(let x = 0; x < n; x++) {
            let sum = 0;
            for(let i = 0; i < n; i++) {
                sum += (matrix1[y][i] * matrix2[i][x])
            }
            newMatrix[y][x] = sum%1000;
        }
    }
    return newMatrix
}

const solution = (arr, count) => {

    let newMatrix = Array.from({length:n},(_,y)=>Array.from({length:n},(_,x)=>x===y ? 1 : 0));
    let matrix = arr.map(v=>[...v]);

    while(count) {
        if(count % 2 === 1) {
            newMatrix = matrixTimes(newMatrix, matrix, n);
            count--;
        }
        matrix = matrixTimes(matrix, matrix, n);
        count = Math.floor(count/2);


    }
    return newMatrix;
}


const answer = solution(arr, b)

for(let i = 0; i < n; i++) {
    console.log(answer[i].join(' '));
}