[백준]1629. 곱셈

[백준]1629. 곱셈

📄 링크

곱셈

---

💡 문제 분석

자연수 A, B, C를 입력 받아 A를 B번 곱한 것을 C로 나눈 나머지를 구하는 문제입니다.
시간 제한이 0.5초이고 B가 21억까지 나올 수 있기 때문에 단순히 21억번을 곱하는 문제는 아닐 거라고 생각했습니다.

분할 정복을 사용해서 홀수일 때와 짝수일 때를 나누어 답을 구해나갔습니다.
절반으로 나눈 값을 곱해줄 때 java의 Math.pow 메서드를 사용했었는데 double 타입을 반환하여 오버플로우가 발생하여 실패했습니다.

오버플로우 방지를 위해 왠만하면 모든 계산에 % C를 해주자

---

⌨️ 코드

import java.util.Scanner;

public class Boj1629_tk {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long A = sc.nextLong();
        long B = sc.nextLong();
        long C = sc.nextLong();
        System.out.println(mul(A, B, C) % C);
    }

    public static long mul(long A, long cnt, long C) {
        if(cnt == 0) return 1;
        if(cnt == 1) return A % C;
        if(cnt % 2 == 1)
            return (A * mul(A, cnt - 1 , C)) % C;
        else {
            long tmp = mul(A, cnt / 2, C);
            return (tmp * tmp) % C;
        }
    }
}

---

📋 회고

• 오버플로우 조심