90 삐약 : 백준 1629| 곱셈 [바킹독| 재귀 |JAVA]

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

 

 

 

 

package BKD_0x0B_Recursion;

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

public class BOJ_1629 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

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

    }

    public static long pow(long a, long b, long c){
        if(b==1) return a%c; // Base Condition
        long val = pow(a, b/2, c);
        val = val*val % c;
        if(b%2 ==0) return val; // b가 짝수일 경우
        return val*a%c; //b 가 홀수일 경우
    }
}

 

❗️시간 복잡도 : O(logb)

 

 

풀이

❗️b가 최대 21억 가까이 될 수 있기 때문에 시간 초과가 발생할 가능성이 다분하다.

 

 

1승을 계산할 수 있다.
k승을 계산했으면 2k승과  2k+1승 또한 O(1)에 계산할 수 있다.

=> a의 임의의 지수승을 귀납적으로 계산 가능하다.

 

 

long val = func(a,b/2,c) * func(a,b/2,c);

 

위와 같이 코드를 구현했을 경우 시간복잡도가 O(b)가 되어 시간 초과가 발생할 수 있다.