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

====

문제 풀이

제곱 횟수가 B가 10억까지 오니 연산을 최소화 시킬 수 있는 방법을 찾아야 한다. 그 중 행렬의 제곱 법칙(?) 을 활용하여 분할 정복으로 푸는 문제였다. a 100번 제곱하는 경우 이것의 결과는 a^50 * a^50 과 같다.

101번 제곱하는 것은 a^100*a^1 과 같다.

즉 입력으로 주언지는 B를 계속해서 반으로 쪼개가면서 내려가는 방식이다.

const recursive = (matrix, powNumber) => {
    if (powNumber === 1) {
        return matrix;
    }
    const temp = recursive(matrix, Math.floor(powNumber / 2));

    let result = multiply(temp, temp);
    if (powNumber % 2 === 1) {
        result = multiply(result, matrix);
    }
    return result;
};

 정답 코드

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, k] = input[0].split(' ').map(Number);

const origin = input
    .slice(1)
    .map((s) => s.split(' ').map((v) => Number(v) % 1000));

const multiply = (a, b) => {
    const result = Array.from({ length: n }, () => Array(n).fill(0));
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            for (let r = 0; r < n; r++) {
                result[i][j] = (result[i][j] + a[i][r] * b[r][j]) % 1000;
            }
        }
    }
    return result;
};

const recursive = (matrix, powNumber) => {
    if (powNumber === 1) {
        return matrix;
    }
    const temp = recursive(matrix, Math.floor(powNumber / 2));

    let result = multiply(temp, temp);
    if (powNumber % 2 === 1) {
        result = multiply(result, matrix);
    }
    return result;
};

const answer = recursive(origin, k);

console.log(answer.map((v) => v.join(' ')).join('\n'));