[백준] 222-풀링 17829 - 분할정복 JAVA

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

17829번: 222-풀링

코드설명

분할정복 문제입니다.

 

문제로직입니다.

1. 0, 0에서 N 을 가지고서 분할정복 재귀가 실행됩니다.

2. map[N][N] 을 -> 4가지 로 나누어서 각 4분면에 해당하는 값들의 2x2가 될떄까지 재귀가 실행됩니다.

3. 마지막에는 결국 각 구간들의 2번쨰로 큰 수가 함수 첫 실행으로 돌아오게 되고 해당값의 arr[2]가 정답이 됩니다.

 

코드

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

public class Main {
	public static int N, M;
	public static int[][] map;
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	map = new int[N][N];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	System.out.println(divideConquer(0, 0, N));
    }
	
	public static int divideConquer(int r, int c, int size) {

		if(size == 2) {
			int[] arr = new int[4];
			int idx = 0;
			for(int i=r; i<r+2;i++) {
				for(int j=c; j<c+2;j++) {
					arr[idx++] = map[i][j];
				}
			}
			Arrays.sort(arr);
			return arr[2];
		}else {
			int[] arr = new int[4];
			int nSize = size/2;
			
			arr[0] = divideConquer(r, c, nSize);
			arr[1] = divideConquer(r , c + nSize, nSize);
			arr[2] = divideConquer(r + nSize, c, nSize);
			arr[3] = divideConquer(r + nSize, c + nSize, nSize);
			
			Arrays.sort(arr);
			return arr[2];
		}
		
	}
	

}