[알고리즘] 백준 1629 곱셈 - 분할정복- 자바

www.acmicpc.net/problem/1629

1629번: 곱셈

 

 

백준 분할정복 단계별풀기 네번째 곱셈 문제를 풀어봤습니다.

처음 단순하게 곱하고 나눠주고 반복문 돌렸다가 시간복잡도 때문에 시간초과가 났습니다. 

분할정복 단계므로 분할해서 재귀를 사용해 풀었습니다.

 

밑 공식대로 풀면 됩니다.

 

출처 : https://onsil-thegreenhouse.github.io/programming/problem/2018/03/29/problem_math_power/

 

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.Scanner;

public class Main {

    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(cal(A, B, C) % C);
    }

    private static long cal(long a, long b, long c) {
        if (b == 0) {
            return 1;
        } else if (b == 1) {
            return a;
        } else if (b % 2 == 0) { //짝수 지수
            long n = cal(a, b / 2, c) % c;
            return (n * n) % c;
        } else { //홀수 지수
            long n = cal(a, b / 2, c) % c;
            return (((n * n) % c) * a) % c;
        }
    }
}

 

 

 

참고 : onsil-thegreenhouse.github.io/programming/problem/2018/03/29/problem_math_power/

[Problem] 어떤 수의 n제곱 구하기(백준 1629번) - Onsil's blog