[백준 24460] 특별상이라도 받고 싶어 (C++)

문제

---

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

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

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

아래 예시를 참고하자.

 

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

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

입력

---

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

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

추첨번호는 2³¹보다 작은 음이 아닌 정수이고, 모든 추첨번호는 서로 다름이 보장된다.

출력

---

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

 

문제 풀이

---

재귀 문제.

 

1/4로 계속 나누어 그 중 두번째로 작은 것을 선택해야 하므로 재귀를 이용한다. 현재 정사각형 길이의 1/2만큼 가로, 세로로 나누면 1/4로 쪼개진다. 시작 위치와 길이를 넘겨 구역에 4개만 남도록 한다. 4개만 남으면 그 중 두 번째로 작은 것을 선택하면 된다.

m이 0도 가능하므로 최초의 N은 1도 가능하다. N이 1일 때를 구현하지 않으면 무한 루프에 빠지므로 주의한다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
using namespace std;
int** arr;
int sortArr[] = { 0, 0, 0, 0 };

int getSecond(int a, int b, int c, int d)
{
	sortArr[0] = a;
	sortArr[1] = b;
	sortArr[2] = c;
	sortArr[3] = d;
	sort(sortArr, sortArr + 4);
	return sortArr[1];
}

int divide(int length, int startX, int startY)
{
	if (length == 1)
	{
		return arr[startX][startY];
	}
	else if (length == 2)
	{
		return getSecond(arr[startX][startY], arr[startX][startY + 1], arr[startX + 1][startY], arr[startX + 1][startY + 1]);
	}
	else
	{
		int nextLength = length / 2;
		int a = divide(nextLength, startX, startY);
		int b = divide(nextLength, startX, startY + nextLength);
		int c = divide(nextLength, startX + nextLength, startY);
		int d = divide(nextLength, startX + nextLength, startY + nextLength);
		return getSecond(a, b, c, d);
	}
}

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

	int N;
	cin >> N;
	arr = new int* [N];
	for (int i = 0; i < N; i++)
	{
		arr[i] = new int[N];
		for (int j = 0; j < N; j++)
		{
			cin >> arr[i][j];
		}
	}
	cout << divide(N, 0, 0) << "\n";
	return 0;
}