[Java] 백준 1629 곱셈 - 분할 정복

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

 

 

 

 

문제 해결 과정

- 단순히 a를 b번 곱하게 된다면 시간 복잡도 O(b) (시간 초과)

- a^b = (a^(b/2))^2  사용하면 해결 가능! (^ : 제곱) 

 

 

작성 코드

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

public class BJ_1629_곱셈 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        long a = Integer.parseInt(st.nextToken());
        long b = Integer.parseInt(st.nextToken());
        long c = Integer.parseInt(st.nextToken());

        // 분할 정복
        System.out.println(pow(a, b, c));

    }

    private static long pow(long a, long b, long c){
        if(b==1){
            return a % c;
        }
        long half = pow(a, b/2, c);
        if(b % 2 == 0){
            return (half*half)%c;
        } else{
            return ((half*half)%c*a)%c;
        }
    }

}

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚