[JAVA] 백준 1629번 : 곱셈

 

---

 

• 코드

정답 코드 : 쉽게보고 했는데 시간초과, 틀렸습니다 등등으로 애먹게 했다...

               해결방법은 곱할때마다 바로 모듈로 연산을 해서 오버플로우를 방지하고

               b값 최대값이 꽤 높게 설정되어 있기때문에 분할정복을 이용한  재귀로 계산방법을 최소화 했다.

 

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
 
        System.out.println(Calculation(a, b, c));
    }
 
    public static long Calculation(int a, int b, int c) {
        if (b == 0) return 1;       
        if (b % 2 == 1) {           
            return Calculation(a, b - 1, c) * a % c;
        } else {                    
            long v = Calculation(a, b / 2, c) % c;
            return v * v % c;
        }
    }
}