[실버 1] 1629번 곱셈 ⭐️

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예시

입력 : 10 11 12
출력 : 4

풀이

단순히 이렇게 풀면 당연히 틀린다!

const fs = require("fs");
let input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .split(" ")
  .map((el) => +el);

let [A, B, C] = input;
let answer = A ** B % C;

console.log(answer);

유의점

이 문제를 풀 때는 두 가지 유의점이 있다.

1. 입력값의 범위가 매우 크다.
2. 숫자가 기하급수적으로 증가할 수 있다. -> 안 그래도 큰 값을 그냥 n제곱한다면 숫자가 매우 커질 수 있으므로 단순히 n제곱 하는 대신 다른 방식을 찾아야 한다.

📌 BigInt

계산값이 자바스크립트 정수 범위를 넘어갈 수 있기 때문에 BigInt라는 것을 써주어야 한다.

BigInt는 길이의 제약 없이 정수를 다룰 수 있게 해주는 숫자형이다.
BigInt형은 숫자를 나타낼 때 다음과 같이 나타내주어야 한다.(둘다 같은 의미)
1. BigInt(1)
2. 1n
https://ko.javascript.info/bigint

📌 A^B % C 연산량 줄이기

모듈로 연산(Modular Arithmetic)의 성질

(A * B) mod C = (A mod C * B mod C) mod C

이를 이용하면 아래와 같은 식이 성립된다.

A * B % C = ((A % C) * (B % C)) % C

B가 짝수일 때 아래와 같은 식이 성립된다.

A^B = A^(B / 2) * A^(B / 2)

ex. 3^4 = 3^2 * 3^2
지수끼리 더해지니까 지수를 2로 나눠서 곱한 것과 같다.

여기에 위에서 나온 성질을 더해주면 아래와 같이 나타낼 수 있다.

A^B % C
= A^(B / 2) * A^(B / 2) % C
= ((A^(B / 2) % C) * (A^(B / 2) % C)) % C

B가 홀수일 때 아래와 같은 식이 성립된다.

A^B = A^(B / 2) * A^(B / 2) * A

ex. 3^5 = 3^2 * 3^2 * 3
홀수는 2로 나눴을 때 항상 1이 남으므로 지수를 2로 나눈 값들에 1을 더해주면 된다.
5 = 2 + 2 + 1, 7 = 3 + 3 + 1

여기에 위에서 나온 성질을 더해주면 아래와 같이 나타낼 수 있다.

A^B % C
= A^(B / 2) * A^(B / 2) * A % C
= ((A^(B / 2) % C) * (A^(B / 2) % C) * (A % C)) % C

풀이

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

const solve = (power) => {
  // B가 1이면 곱하나마나니까 바로 A%C 출력
  if (power === 1n) {
    return A % C;
  }
  // B를 2로 나눈 값을 입력하여 함수를 재귀적으로 호출한다.
  const half = solve(power / 2n) % C;

  // B를 2로 나눈 나머지가 1이면(홀수면) ((A^(B / 2) % C) * (A^(B / 2) % C) * (A % C)) % C 를 적용한다.
  if (power % 2n) {
    return (half * half * (A % C)) % C;
  }

  // B가 짝수면 ((A^(B / 2) % C) * (A^(B / 2) % C)) % C 를 적용한다.
  return (half * half) % C;
};

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

메모리 : 9332KB
시간 : 120ms

풀이 참조
https://tesseractjh.tistory.com/249

node.js 입력 방법 참조
https://velog.io/@eundada064/%EB%B0%B1%EC%A4%80-JavaScript-VSCode-%ED%99%98%EA%B2%BD-%EC%84%B8%ED%8C%85