[백준 JAVA] 1629. 곱셈

문제 링크

---

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

접근 방법

---

단순히 a^b % c를 계산하면 b가 매우 클 경우 연산량이 많아지고 오버플로우가 발생할 수 있습니다.
이를 해결하기 위해 분할 정복을 이용한 거듭제곱 (modular exponentiation) 방식으로 계산해야 합니다.

Java에서는 BigInteger의 modPow() 메서드를 사용하면 쉽게 해결할 수 있습니다.
a.modPow(b, c)는 (a^b) % c를 빠르고 정확하게 계산해줍니다.

소스 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        BigInteger a = new BigInteger(st.nextToken()), b = new BigInteger(st.nextToken()), c = new BigInteger(st.nextToken());

        System.out.println(a.modPow(b, c));
    }
}

코드 설명

---

입력된 수를 BigInteger로 처리하고,
modPow() 메서드를 사용해 (a^b) % c 값을 바로 출력합니다.
내장 메서드를 활용함으로써 복잡한 분할 정복 로직 없이도 효율적으로 문제를 해결할 수 있습니다.