[백준] 1629번 - 곱셈 [Java]

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

 

[백준] 1629번 - 곱셈 [Java]

---

1.  아이디어

 

A^B % C를 구하는 문제로 B가 짝수면 A^B = (A^(B/2)) * (A^(B/2)), B가 홀수면 A^B = (A^(B/2)) * (A^(B/2)) * B인 점을 이용하면 B가 큰 수여도 빠르게 계산할 수 있다.

---

2. 문제풀이

 

아이디어의 연산이 B/2에 대해서도 똑같이 반복되므로 이를 재귀 함수로 구현했다. B가 자연수이므로 재귀과정에서 B가 1이 될때가 종료조건이 되고 짝수, 홀수 여부에 따라 재귀를 해주면 된다. 이때 오버플로우가 발생할까봐 long 타입으로 처리를 했고 중간중간 C로 모듈러 연산을 해줘서 long 타입으로 선언해도 오버플로우가 발생할 수 있는 부분을 방지했다.

---

3. 코드

 

import java.io.*;
import java.util.*;

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());

        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        long C = Long.parseLong(st.nextToken());

        System.out.println(recur(A, B, C));
    }

    private static long recur(long A, long B, long C) {
        if (B == 1) return A % C;

        long half = recur(A, B / 2, C);

        if (B % 2 == 0) return half * half % C;
        else return half * half % C * A % C;
    }

}

---

4. 후기