분할정복

설계 전략

• 분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다.
• 정복(Conquer) : 나눈 작은 문제를 각각 해결한다.
• 통합(Combine) : (필요하다면) 해결된 해답을 모은다.

💡 [분할 - 정복 - 통합]까지 하면 '병합정렬'
💡 [분할 - 정복]까지 하면 '퀵정렬'

분할 정복 기법

분할정복 | 거듭제곱

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int result, x, n;
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        for(int t=1; t<=10; t++) {
            int tc = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
             
            x = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
             
             
            System.out.println("#"+tc+" "+power(x, n));
        } 
    }
     
    static int power(int x, int n) {
        if(n == 1) return x;
         
        result = power(x, n/2);
        if(n%2==0) {
            return result*result;
        } else {
            return result*result*x;
        }
    }
 
}