#17829 : 222-풀링

풀이방법

사용된 것:

분할정복

재귀

 

2022.06.04

재귀적으로 정의된 분할정복 함수 solve를 사용하였다.

 

solve는 한 변의 길이가 $2^n$인 정사각형 모양의 특정 영역을 맡아서,

자신이 맡은 영역의 한 변의 길이가 2라면, 그 영역에 들어있는 4개의 수 중 두 번째로 큰 값을 리턴한다.

반대로 자신이 맡은 영역의 한 변의 길이가 2보다 크다면, 영역을 동일한 4개 구역으로 쪼개어 그 4개 구역에 대한 재귀를 수행하여 결과값 4개를 받아온다. 그 후 그 결과값 4개 중 두 번째로 큰 값을 리턴한다.

 

코드

Java(2022.06.04)

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

public class Main {
	
	static int[][] matrix;	//전체 행렬
	//네 부분으로 재귀 시 쪼개기 위한 좌표변경용 배열
	static int[] r = {0, 0, 1, 1};
	static int[] c = {0, 1, 0, 1};
	
	
	//분할정복 함수 (맡은 영역에서 두 번째로 큰 수를 리턴)
	static int solve(int row, int col, int len) {
		//row와 col은 영역의 첫칸의 좌표, len은 영역의 한 변의 길이
		
		//한 변의 길이 2의 영역까지 쪼개졌을 경우 두 번째로 큰 수 찾아서 리턴
		if(len == 2) {
			int[] sort = new int[4];
			for(int i=0; i<4; i++) sort[i] = matrix[row+r[i]][col+c[i]];
			Arrays.sort(sort);
			return sort[2];
		}
		
		//한 변의 길이 2 초과의 영역이 주어졌을 경우 넷으로 쪼개어 재귀한 뒤,
		//그 네 개 재귀함수의 결과값들 중 두 번째로 큰 것을 리턴
		int next = len/2;
		int[] sort = new int[4];
		for(int i=0; i<4; i++) sort[i] = solve(row+(r[i]*next), col+(c[i]*next), next);
		Arrays.sort(sort);
		return sort[2];
	
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//입력값 읽어오기
		int n = Integer.parseInt(br.readLine());
		matrix = new int[n][n];
		for(int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<n; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		//분할재귀 함수 수행
		int answer = solve(0, 0, n);
		//정답 출력
		System.out.print(answer);
	}

}