[백준 알고리즘] Node.js 2740. 행렬 곱셈

1. 문제

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

2740번: 행렬 곱셈

 

2. 풀이

- 행렬의 곱셈을 이용한 문제이다.

- 행렬의 곱셈 관련된 부분은 아래의 페이지를 참고했다.

https://pasus.tistory.com/7

 

- 처음 나의 풀이 : 결과 - 출력 초과

const inputs = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [an,am] = inputs.shift().split(' ').map(v => +v);
const aArr = inputs.splice(0,an).map(v => v.split(' ').map(Number));
const [bm,bk] = inputs.shift().trim().split(' ').map(v => +v);
const bArr = inputs.splice(0,bm).map(v => v.split(' ').map(Number))

const total = Array.from({length : an}, () => new Array(bk).fill(0));

const recursive = (y,x) => {
  if(x >= bk) return;

  while(y < an){
    for(let i = 0; i < am; i++){
      console.log(y, x, aArr[y][i], bArr[i][x])
      total[y][x] += aArr[y][i] * bArr[i][x];
    }
    y++;
  }
  
  recursive(0, x+1)
}

recursive(0,0)

const answer = total.map(v => v.join(' ')).join('\n')

console.log(answer)

- vscode에서 작성하였을 때 주어진 테스트 케이스는 문제없이 통과했지만 제출하였을 때 출력 초과가 발생하였다.

 

 

- 다른 사람의 풀이 : https://lhoiktiv.tistory.com/384

const fs = require('fs');
const input = fs.readFileSync("./dev/stdin").toString().trim().split("\n").map(v=>v.split(' ').map(x=>+x)); 

const A=[]; //첫번째 행렬
const B=[];  // 두번째 행렬
const C =[]; // 계산하기 좋게 두번째 행렬을 바꿔서 만들 행렬

//첫번째 행렬 정리
const [N,M] = input.shift();  
for(let i = 0; i<N; i++){
  A.push(input.shift());
}

//두번째 행렬 정리
const [K,L] = input.shift();
for(let i = 0; i<K; i++){
  B.push(input.shift());
}

//두번째 행렬 수정
 while(B[0].length>0){
   const temp = [];
   for(let i = 0; i<K;i++){
    temp.push(B[i].shift())
   }
   C.push(temp)
 }

 // 행렬의 곱셈
 const answer = [];
 for(let i = 0; i<N; i++){
  answer.push([])
   const X = A[i];
   for(let j = 0; j<L; j++){
     let sum = 0;
    const Y = C[j]
     for(let k = 0; k<K; k++){
      sum+=X[k]*Y[k];
     }
     answer[answer.length-1].push(sum)
   }
 }

 const result = answer.map(v=>v.join(' ')).join('\n')

 console.log(result)

 

 

 

 

3. 정리

- 내 풀이는 주어진 조건과 짧은 테스트 케이스의 경우에는 통과하는 것 같다.

- 크기가 큰 행렬의 경우에 출력 초과가 발생하는 것 같은데.... 재귀를 사용해서 그런건가 정확한 이유를 모르겠다.

나중에 다시 풀어봐야겠다.