<백준> 24460

특별상이라도 받고 싶어

문제
HCPC 2021에 참석한 $N \times N$명의 사람들이 의자가 정사각형 형태로 배치된 대회장에서 대회를 한다. 모든 의자에는 서로 다른 추첨번호가 적혀있으며 HCPC 2021의 마지막에는 아래에 설명된 규칙에 따라 특별상을 받을 사람 한 명을 정한다. 특별상을 받을 수 있는 사람이 한 명이라면, 그 사람이 뽑힌다.
그렇지 않은 경우, 대회장을 같은 크기의 정사각형 네 개로 나누어 각 구역에서 이 규칙을 재귀적으로 적용해서 구역마다 한 명씩 총 네 명을 뽑는다.
뽑힌 네 명 중 의자에 적힌 추첨번호가 두 번째로 작은 사람이 뽑힌다.
HCPC 2021에 참가한 지원이는 자신의 실력이 부족해서 수상권이 아니라고 생각하였고, 실력과 무관하게 받을 수 있는 특별상을 노리고 있다.
아래 예시를 참고하자.

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

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

입력
첫 번째 줄에는 정수 $N$이 주어진다. (단, $N = 2^m$, $0 \le m \le 10$, $m$은 정수)두 번째 줄부터 $N$개 줄의 $i$번째 줄에는
$i$번째 줄에 있는 의자에 적힌 추첨번호가 주어진다. 각 줄에는 $N$개의 추첨번호가 공백으로 구분되어 주어진다.
추첨번호는 $2^{31}$ 보다 작은 음이 아닌 정수이고, 모든 추첨번호는 서로 다름이 보장된다.

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

앞의 분할정복 문제와 똑같이 풀면 된다. 하지만 계속 틀리길래 뭔가 하고 봤더니 1일때의 예외처리를 해줘야 했어야 한다.

int board[1024][1024];

int divide(int x, int y, int size)
{
    if(size == 1)
        return board[x][y];
	if (size == 2)
	{
		vector<int> v;
		for (int i = x; i < x + 2; i++)
		{
			for (int j = y; j < y + 2; j++)
			{
				v.push_back(board[i][j]);
			}
		}
		sort(v.begin(), v.end());
		return v[1];
	}

	vector<int> temp;
	int newSize = size / 2;
	temp.push_back(divide(x, y, newSize));
	temp.push_back(divide(x, y+newSize, newSize));
	temp.push_back(divide(x+newSize, y, newSize));
	temp.push_back(divide(x+newSize, y+newSize, newSize));
	sort(temp.begin(), temp.end());
	return temp[1];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> board[i][j];
		}
	}
	cout<< divide(0, 0, n);
}