[백준 1629 - Node.js] 곱셈

🔗 문제 링크

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

1629번: 곱셈

✏️ 풀이

const [A, B, C] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split(' ')
  .map(BigInt);

const solve = (power) => {
  if (power === 1n) {
    return A % C;
  }
  
  const half = solve(power / 2n) % C;

  if (power % 2n) {
    return (half * half * (A % C)) % C;
  }

  return (half * half) % C;
};

console.log(solve(B).toString());

모듈로 연산(Modular Arithmetic)의 성질에 의하면 (A * B) mod C = (A mod C * B mod C) mod C가 성립한다. 즉, A * B를 C로 나눈 나머지는 (A를 C로 나눈 나머지 * B를 C로 나눈 나머지)를 C로 나눈 나머지와 같다는 뜻이다.

 

A^B는 B가 짝수라면 A^(B / 2) * A^(B / 2)로 나타낼 수 있는데, 위 모듈러 연산의 성질을 활용하여 A^B % C = ((A^(B / 2) % C) * (A^(B / 2) % C)) % C가 성립함을 알 수 있다. B가 홀수일 때는 A^B를 A^[B / 2] * A^[B / 2] * A로 나타낼 수 있고, A^B % C = ((A^(B / 2) % C) * (A^(B / 2) % C) * (A % C)) % C가 성립함을 알 수 있다.

 

이러한 수학적 성질을 활용하여 주어진 B를 반으로 계속 나누면서 A^B의 연산을 (A^(B / 2))^2 또는 (A^[B / 2])^2 * A로 만들고 나머지 연산을 미리 진행할 수 있다. 즉, A^B % C를 직접 계산하지 않아도 (A^(B / 2) % C)^2 % C 또는 (A^[B / 2] % C)^2 * (A % C)를 통해 동일한 값을 구할 수 있다.

(짝수 ex: 2^10 % 7 = ((2^5 % 7) * (2^5 % 7)) % 7 = (32 % 7)^2 % 7 = 4^2 % 7 = 2)

(홀수 ex: 2^9 % 7 = ((2^4 % 7) * (2^4 % 7) * (2 % 7)) % 7 = ((16 % 7)^2 * 2) % 7 = 4 * 2 % 7 = 1)

 

실제 연산은 A^(B / 2) 또는 A^[B / 2]를 한 번 계산한 값(half)을 재활용하기 때문에 연산의 양이 기하급수적으로 줄어들게 된다. (만약 A를 진짜로 B번 곱하면서 값을 구하려면 문제의 조건 때문에 최대 2,147,483,647번의 연산이 일어나게 되어 시간 초과가 나게 된다.)

 

문제의 조건에서 A, B, C는 2,147,483,647 이하의 자연수라고 하였는데, C로 나눈 나머지끼리의 곱이 자바스크립트 Number 타입의 안전한 정수의 최댓값인 9007199254740991를 초과할 수 있기 때문에 BigInt를 사용하였다. BigInt는 BigInt끼리만 연산이 되기 때문에 작은 수여도 BigInt와 연산을 하려면 BigInt형으로 변환(BigInt(숫자) 또는 숫자 뒤에 n을 붙인 리터럴)해서 연산을 해야 한다. 그리고 마지막에 값을 출력할 때에는 BigInt 리터럴 뒤에 알파벳 n이 같이 출력되기 때문에 문자열로 변환하여 n을 제거해야 한다.

 

참고 자료

https://sweetdev.tistory.com/807

[정보보안] 모듈로 계산의 성질 (modular)