분할 정복 기법

반으로 나누어 각각 해결하고 또 나누어 해결하는 식을 반복하여 마지막에 통합하여 해답을 찾는다.

package com.ssafy.w0817;

import java.util.Scanner;

//분할 정복 알고리즘과 재귀 비교
//호출횟수만 비교하기 위해 코딩한 것(값의 오버플로우 생각하지 않고)
//분할정복이 월등히 적은 횟수
public class SquareNumber_분할정복 {
	
	//재귀
	static int callCnt;
	static long exp1(long x,long y) {
		callCnt++;
		if(y==1) return x;
		
		return x *exp1(x, y-1);
	}
	
	// 분할정복
	static long exp2(long x,long y) {
		callCnt++;
		
		if(y==1) return x;
		
		long r = exp2(x,y/2);
		long res = r*r;
		
		if(y%2==1) res *= x; // 홀수일때
		
		return res;
	}
	
	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();
		
//		System.out.println(exp1(x,y));
		System.out.println(exp2(x,y));
		System.out.println(callCnt);
		
	}

}