[JavaScript/재귀] 백준 실버 1 : 1629 - 곱셈

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

1629번: 곱셈

---

📌 작성한 코드

// 1629
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
let input = fs.readFileSync(filePath).toString().trim();
let [A, B, C] = input.split(" ").map(Number);

// a^n * a^n = a^2n
// a^b/2 * a^b/2 = a^b -> 이 방식 이용하기

const pow = (a, b, c) => {
    a = BigInt(a);
    c = BigInt(c);
    if (b === 1) return a % c;
    let val = pow(a, Math.floor(b / 2), c);
    val = (val * val) % c; // 더 작게 쪼갠 값을 통해 더 큰 값 구하기
    if (b % 2 === 0) return val; // 짝수면 그대로
    return (val * a) % c; // 홀수면 한번 더 곱해주기
};

console.log(pow(A, B, C).toString());

 

📌 풀이 

(a^b) mod c를 구하는 문제이다. 문제 자체는 간단하지만 직관적인 방법으로 풀면 시간 초과와 오류가 발생해서 다른 방법을 사용해야한다.

 

이번 문제에서는 재귀를 사용해서 풀어볼 것이다. 

우리는 a^b % c를 구하고 싶지만 b의 크기가 2,147,483,647까지 가능한 상황에서 그만큼 곱셈을 여러번 하게되면 해당 값의 범위가 자바스크립트가 표현할 수있는 숫자의 범위를 넘을 수 있을 뿐 아니라, 너무 많은 시간이 소요될 것이다. 그래서 a^b % c를 귀납법을 통해 더 간단하게 계산할 수 있는 방법을 찾아보자.

(a^b) * (a^b) = a^2b
(a^b/2) * (a^b/2) = a^b

해당 곱셈을 쪼개보면 이렇게 나오는 것을 확인 할 수 있다. a를 b번 제곱하는 것이 아니라, b를 2로 나눈 횟수만큼 제곱하고, 그 값을 제곱해도 원하는 값을 구할 수 있다는 것이다. 그렇다면 우리는 계속해서 저 많은 b번을 곱할 필요없이, 계속해서 b를 2로 나누면서 1이 될 때까지 반복하고, 다시 뒤로 돌아서 구한 값을 제곱하면서 우리가 원하는 값으로 만들어 가는 것이다. 

// b가 1이 될때까지 계속 2로 나누기
a=3 b=5 c=2

b=5 : 3^5 % 2
b=5/2(2) : 3^2 % 2
b=2/2(1) : 3^1 % 2

// 다시 뒤로 돌아서 원래 원하는 값 구해주기
b=1 : 3^1 % 2 = 1
b=2 : b가 1일때 값^2 = 1^2 % 2 = 1
b=5 : b가 2일때 값^2 = 1^2 % 2 = 1
-> 답 = 1

 

그리고 b가 홀수라 나누기 2가 딱 떨어지지 않는 경우는 a를 한 번 더 곱해서 값을 맞춰준다.

if (b % 2 === 0) return val; // 짝수면 그대로
return (val * a) % c; // 홀수면 한번 더 곱해주기

 

또한 주의해야 할 부분은 계산하다가 자바스크립트가 표현할 수 있는 값인 2^53-1의 값을 초과하는 값을 저장해야 하는 상황이 발생할 수 있으므로, a와 c를 BigInt를 사용해서 해당 값을 초과하는 값이 나오더라도 제대로 저장될 수 있도록 해주어야 한다. (이 부분을 해주지 않으면 틀렸습니다가 나온다!) 그리고 BigInt의 마지막에는 n이 붙어있기 때문에 `toString`을 통해 원하는 형태의 숫자값으로 변환해서 출력해주어야 한다.

 

✅ 성공