[BOJ][C++] 백준 24460번: 특별상이라도 받고 싶어

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

 

문제

HCPC 2021에 참석한 N×N$N \times N$명의 사람들이 의자가 정사각형 형태로 배치된 대회장에서 대회를 한다. 모든 의자에는 서로 다른 추첨번호가 적혀있으며 HCPC 2021의 마지막에는 아래에 설명된 규칙에 따라 특별상을 받을 사람 한 명을 정한다.

1. 특별상을 받을 수 있는 사람이 한 명이라면, 그 사람이 뽑힌다.
2. 그렇지 않은 경우, 대회장을 같은 크기의 정사각형 네 개로 나누어 각 구역에서 이 규칙을 재귀적으로 적용해서 구역마다 한 명씩 총 네 명을 뽑는다.
3. 뽑힌 네 명 중 의자에 적힌 추첨번호가 두 번째로 작은 사람이 뽑힌다.

HCPC 2021에 참가한 지원이는 자신의 실력이 부족해서 수상권이 아니라고 생각하였고, 실력과 무관하게 받을 수 있는 특별상을 노리고 있다.

아래 예시를 참고하자.

 

위와 같은 의자 배열이 있다고 가정하자. 이를 네 개의 구역으로 나누면 아래와 같다.

 

나누어진 구역의 왼쪽 위 구역을 다시 네 개의 구역으로 나누면 아래와 같다.

 

여기에서 추첨번호가 두 번째로 낮은 사람을 고르면 아래와 같다.

 

이와 같은 작업을 모든 영역에 대해 실행하면 아래와 같다.

 

따라서 특별상을 받는 추첨번호는 아래와 같다.

 

따라서, 추첨번호 3$3$이 적힌 의자에 앉은 참가자가 특별상을 받는다.

의자 각각에 적혀 있는 추첨번호가 주어질 때, 지원이가 HCPC 2021에서 경품을 받을 수 있으려면 어떤 의자에 앉아야 하는지 계산하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 정수 N$N$이 주어진다. (단, N=2m$N = 2^m$, 0≤m≤10$0 \le m \le 10$, m$m$은 정수)

두 번째 줄부터 N$N$개 줄의 i$i$번째 줄에는 i$i$번째 줄에 있는 의자에 적힌 추첨번호가 주어진다. 각 줄에는 N$N$개의 추첨번호가 공백으로 구분되어 주어진다.

추첨번호는 231$2^{31}$ 보다 작은 음이 아닌 정수이고, 모든 추첨번호는 서로 다름이 보장된다.

출력

지원이가 HCPC 2021에서 경품을 받기 위해 앉아야 하는 의자에 적힌 추첨번호를 출력한다.

 

풀이

재귀함수를 이용한 분할정복 문제

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int recur(int a, int b, int c, int d, vector<vector<int>>&v) {
    if(a==c & b==d) {
        return v[a][b];
    }
    
    int x = (c+a)/2;
    int y = (d+b)/2;
    
    vector<int>tmp(4);
    tmp[0] = recur(a,b,x,y, v);
    tmp[1] = recur(a,y+1,x,d, v);
    tmp[2] = recur(x+1,b,c,y, v);
    tmp[3] = recur(x+1,y+1,c,d, v);
    
    sort(tmp.begin(), tmp.end());
    return tmp[1];
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>>v(n, vector<int>(n));
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> v[i][j];
        }
    }
    
    cout << recur(0,0,n-1,n-1, v);
    
    
    return 0;
}