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

풀이 아이디어

재귀랑 분할정복을 활용한 문제이다.
좌석의 번호를 저장한 2차원 배열을 4등분 하면서
2번째로 작은 배열만 남기면서 마지막에 1개가 남았을 때 출력하는 방식이다.

풀이 코드

import java.io.*;
import java.util.*;

public class _24460 {
    static int[][] seats;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        seats = new int[n][n];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                seats[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.println(divideQuarter(n, 0, 0));
    }

    static int divideQuarter(int n, int x, int y){
        // 재귀적으로 4등분 해서 각 구역의 2번째로 작은 값 찾기
        // 종료 조건
        if(n == 1){
            return seats[x][y];
        }
        else{
            // 2차원 행렬은 4등분함.
            int[] dividedSeats = new int[]{
                divideQuarter(n/2, x, y),
                divideQuarter(n/2, x, y+n/2),
                divideQuarter(n/2, x+n/2, y),
                divideQuarter(n/2, x+n/2, y+n/2)
            };
            Arrays.sort(dividedSeats);
            return dividedSeats[1];
        }
    }
}