[백준1629_자바스크립트(javascript)] - 곱셈

🔴 문제

곱셈

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [a, b, c] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split(' ')
  .map(BigInt);

function recursive(a, n) {
  if (n === 0n) return 1n;
  if (n === 1n) return a % c;

  if (n % 2n === 0n) {
    let result = recursive(a, n / 2n);
    return (result * result) % c;
  } else {
    let result = recursive(a, (n - 1n) / 2n);
    return (result * result * a) % c;
  }
}

console.log(recursive(a, b).toString());

🟢 풀이

⏰ 소요한 시간 : -

분할 정복을 이용한 거듭제곱이라는 알고리즘을 학습하고 풀이했다..!
a를 b번 곱하는데에 시간이 너무 오래걸리기 때문에 a를 b/2번 곱하고 이 결과끼리 곱하는 방식이다.
만약 b가 짝수라면 위에서 말한대로 진행하면 되지만 b가 홀수라면 b에서 1을 빼 짝수로 만들어 위의 방식대로 구현한 뒤 a를 한번 곱해주면 된다.
위의 방식을 재귀호출로 구현했다. a는 곱해지는 값이고, n은 몇 번 곱해야되는지 세어주는 수다. 종료 조건은 a의 0승이거나 1승일 때 이다. a의 0승은 1을 리턴, 1승은 a를 리턴 해준다. n이 2보다 클 때는 짝/홀에 따라서 재귀호출을 해주면 된다. 마지막으로는 toString() 으로 문자열로 바꾸어서 출력하면 된다.

참고로 큰 수를 계산하는 작업도 시간이 소요되는 작업이라고 한다. 따라서 모든 연산에 모듈러 연산을 적용하여 풀이한다.

🔵 Ref