문제 설명

자연수 A를 B번 곱한 수에 C로 나눈 나머지를 구하는 프로그램을 작성

Input 제한

A, B, C는 모두 2,147,483,647이하의 자연수

예제

10 11 12 => 4

풀이

재귀

• 2^4 = (2^2)x(2^2)의 패턴을 이용한다. 제곱의 수가 0이 될 때까지 2로 나누어 재귀 요청을 한다.
• 제곱의 수가 짝수일 경우 2로 나눈 수를 서로 곱한다.
  2^4 = (2^2)x(2^2) => (2^1)x(2^1)x(2^1)x(2^1)
• 만일 제곱의 수가 홀수일 경우 2로 나눈 수를 서로 곱하고 A를 한번 더 곱해준다.
  2^5 = (2^2)x(2^2)x2 => (2^1)x(2^1)x(2^1)x(2^1)x2
• 매번 재귀를 할 때마다 C의 값을 나눈 뒤 나머지 값을 구해준다.
  (2^4)%C = (2^2%C)x(2^2%C)
• BigInt를 사용하여 Number가 나타낼 수 있는 2^53 - 1의 값 보다 클 경우를 대비 한다.

  BigInt란? Number의 최대 수보다 클 경우를 방지 할 수 있는 내장 객체

const fs = require("fs");
const [A, B, C] = fs
  .readFileSync("./input.txt")
  .toString()
  .trim()
  .split(" ")
  .map(BigInt);

function Power(x, y) {
  if (y === BigInt(0)) return BigInt(1); 
  // y의 값이 0일 경우 1을 리턴

  let pow = Power(x, BigInt(parseInt(y / BigInt(2)))); 
// 2^2 => (2^1)x(2^1) 패턴을 재귀 (parseInt로 소수점 처리 후, 다시 BigInt로 변경)
  if (y % BigInt(2) === BigInt(0)) {
    return (pow * pow) % C; // 짝수 일 경우
  } else {
    return (pow * pow * x) % C; // 홀수 일 경우
  }
}
console.log(parseInt(Power(A, B))); // BigInt => Number

회고

2^2 => (2^1)x(2^1)의 패턴은 알았으나, BigInt를 통해서 Number값보다 초과 할 경우의 사용하는 방법을 알고, 2^2%C => (2^1%C)x(2^1%C)의 값이 같은 패턴도 배웠다. 또, 재귀는 매번 풀어도 패턴을 찾기가 가장 어려운 것 같다 더 많은 문제들을 풀어서 패턴을 찾아가는 연습을 더 해봐야겠다.
참고자료1
참고자료2