[백준/1629/node.js] 곱셈

문제

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

풀이

처음에 냅다 A를 B번 곱하는 식으로 풀었는데 시간초과가 나와서(실버 1인데 그렇게 간단할 리가 없지😭) 무슨 알고리즘을 사용하는 건가 싶었다. 하긴 숫자 범위가 1 ~ 2,147,483,647까진데 O(n)으로 구하면 시간초과가 날 법 하다. 그래서 알고리즘 분류를 봤더니 분할 정복을 이용한 거듭제곱이라고 나와있었다. 분할 정복 알고리즘을 처음 접해서 정리해보기로 했다!

분할 정복 알고리즘

분할 정복 알고리즘이란 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘을 말한다.

예를 들어서 2¹¹ 을 구하는 경우, 2를 11번 곱하는 방식으로 구할 수도 있지만(11번 계산)

2¹¹ = 2⁵ * 2⁵ * 2
2⁵ = 2² * 2² * 2
2² = 2¹ * 2¹

이렇게 세 번의 연산만으로도 구할 수 있다!

Aⁿ = Aⁿᐟ² * Aⁿᐟ²                (n이 짝수인 경우)
Aⁿ = A⁽ⁿ⁻¹⁾ᐟ² * A⁽ⁿ⁻¹⁾ᐟ² * A    (n이 홀수인 경우)

즉 분할 정복 거듭제곱은 이런 식으로 만들어진다.

코드 작성하기

function power(base, exponent) {
  if (exponent === 1) {    
    return base;            
  } else if (exponent % 2 === 0) {
    let byTwo = power(base, exponent / 2);
    return byTwo * byTwo;
  } else {
    let byTwoPlusOne = power(base, (exponent - 1) / 2);
    return byTwoPlusOne * byTwoPlusOne * base;
  }
}

하지만 위의 문제의 내용처럼 구하려는 수가 매우 커질 수 있으므로 보통 어떤 수(예를 들면 N)로 나눈 나머지를 구한다.

function power(base, exponent) {
  if (exponent === 1) {
    return base % N;
  } else if (exponent % 2 === 0) {
    let byTwo = power(base, exponent / 2) % N;
    return (byTwo * byTwo) % N;
  } else {
    let byTwoPlusOne = power(base, (exponent - 1) / 2) % N;
    return (((byTwoPlusOne * byTwoPlusOne) % N) * base) % N;
  }
}

모듈로 연산에 의해 (A * B) % C = (A % C * B % C) % C가 성립한다.
따라서 수가 너무 커질 수 있기 때문에 계산할 때 마다 나머지로 계산해준다!

그래서 위의 코드를 이용해서 정답을 제출했는데.. 자꾸 1%에서 틀리는 것이였다 ㅠㅠ 아마도 수의 범위가 너무 커서 자바스크립트의 출력 범위를 넘어서는 것 같았다. 그래서 BigInt를 사용하기로 했다.

정답 코드

let fs = require("fs");
let [A, B, C] = fs
  .readFileSync("/dev/stdin")
  .toString()
  .split(" ")
  .map(BigInt);   // BigInt로 형변환 해준다.

function power(base, exponent) {
  if (exponent === 1n) {   // BigInt라서 BigInt로 비교
    return base % C;
  } else if (exponent % 2n === 0n) { // BigInt로 연산
    let byTwo = power(base, exponent / 2n) % C;
    return (byTwo * byTwo) % C;
  } else {
    let byTwoPlusOne = power(base, (exponent - 1n) / 2n) % C;
    return (((byTwoPlusOne * byTwoPlusOne) % C) * base) % C;
  }
}

console.log(power(A, B).toString()); 
// 숫자에 붙은 n을 떼줘야 해서 toString()을 해준다!