[Baekjoon 24460 / Java / 실버3] 특별상이라도 받고 싶어

 

분할 정복 문제이다.

 

N * N 형태의 좌석과 추첨번호가 주어진다.

여기서 N은 2의 0승 ~ 2의 10승 중 하나이고, 따라서 정사각형 형태이며 4등분으로 분할이 가능하다.

 

특별상은 딱 한명만 받을 수 있다.

사람이 1명밖에 없다면 그 사람이 수상한다.

사람이 4명이라면(N : 2) 4명 중 추첨번호가 2번째로 작은 사람이 수상한다.

사람이 16명(N : 4) 이상이라면, 각 구역에 사람이 4명만 남을 때까지 4등분한 후, 각 구역마다 2번째로 작은 사람을 가려내고, 그렇게 추려진 사람들 중에서 또 2번째로 작은 사람을 가려내고.. 하는 형태로 진행한다.

 

예시

 

위 그림에선 왼쪽 위 : 1 , 오른쪽 위 : 3, 왼쪽 아래 : 5, 오른쪽 아래 : 7 이다.

이렇게 추첨된 1, 3, 5, 7 중에서 또 2번째로 작은 번호를 고른다. 즉 답은 3이 된다.

 

 

import java.io.*;

import java.util.*;

public class 특별상이라도_받고_싶어_24460 {

    public static void main(String[] args) throws Exception {

       

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

       

        // x, y의 길이

        int N = Integer.parseInt(br.readLine());

        // 좌석별 추첨번호 입력받기

        int board[][] = new int[N][N];

        StringTokenizer st;

        for(int i = 0; i < N; i++) {

            st = new StringTokenizer(br.readLine());

            for(int j = 0; j < N; j++) {

                board[i][j] = Integer.parseInt(st.nextToken());

            }

        }

        System.out.println(special(0, 0, N, board));

    }

    // 시작 좌표, 변의 길이, 좌석별 추첨번호 입력받기

    public static int special(int x, int y, int N, int[][] board) {

       

        // 사람이 1명이면 그 사람을 뽑는다

        if(N == 1) {

            return board[0][0];

        }

        // 사람이 4명이면 번호가 2번째로 작은 사람 고르기

        if(N == 2) {

            int arr[] = new int[4];

            int index = 0;

            for(int i = x; i < x + N; i++) {

                for(int j = y; j < y + N; j++) {

                    // 배열에 4개의 추첨번호를 저장

                    arr[index++] = board[i][j];

                }

            }

            // 정렬 후 2번째로 작은 값 리턴

            Arrays.sort(arr);

            return arr[1];

        }

        // 사람이 4명보다 많다면 4등분으로 나누어 추첨번호 고르기

        else {

            int arr[] = new int[4];

            arr[0] = special(x, y, N/2, board);

            arr[1] = special(x, y + N/2, N/2, board);

            arr[2] = special(x + N/2, y, N/2, board);

            arr[3] = special(x + N/2, y + N/2, N/2, board);

            // 고른 번호 중 2번째로 작은 값 리턴

            Arrays.sort(arr);

            return arr[1];

        }

    }

}

 

재귀함수를 이용한 분할 정복으로 해결할 수 있다.

 

사람이 1명이면 바로 그 사람이 수상, 4명이면 4명 중 2번째로 작은 사람을 고른다

16명 ( N : 4 ) 이상이면 재귀함수를 통해 4명이 될 때까지 4개로 나눈 후 2번째로 작은 사람을 고르고, 그 중에서 2번째로 작은 사람을 고른다.