[백준] 1629

곱셈

문제

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

입력

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

출력

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

풀이

const recurMul = (a, b, m) => {
  if (b === BigInt(0)) return BigInt(1);
  if (b % BigInt(2) === BigInt(1))
    return (a * recurMul(a, b - BigInt(1), m)) % m;
  let val = recurMul(a, BigInt(b / BigInt(2)), m) % m;
  return (val * val) % m;
};

const mul = () => {
  let input = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split(" ")
    .map(BigInt);
  console.log(String(recurMul(input[0], input[1], input[2])));
};

mul();

반성회

1. b를 1씩 줄여나가는 재귀 (recurMul(a, b - 1, m)) 은 시간이 굉장히 오래걸린다
2. 따라서 b를 1/2씩 줄여나가되, 만약 b가 2로 나누어떨어지지 않는다면 b - 1의 결과값에 a를 한번 더 곱해서 m으로 나누는 식으로 +1을 맞춰준다 (2로 나눈 나머지는 0이 아니면 무조건 1이므로)
3. if (b % BigInt(2) === BigInt(1)) return (a * recurMul(a, b - BigInt(1), m)) % m;
4. 입력값의 범위가 a, b, m 모두 2147483647 이하의 자연수이므로 큰 수 연산이 필요하다다만 BigInt를 사용할 땐 사칙연산에 사용되는 다른 숫자들 모두 BigInt여야 연산이 된다 (아니면 컴파일 에러)
5. 이는 BigInt를 사용하여 해결할 수 있다
6. 아슬아슬하게 시간 제한에 맞출 수 있다다만 정답코드 보니까 그렇게 큰 차이는 안난다 자바스크립트가 원래 느리긴 하다
7. DP (동적계획법) 를 사용하면 더 빠르게 풀 수 있는 것 같긴 하다