| 시간 제한 | 메모리 제한 |
| 1초 | 512MB |
문제
농부 존의 N마리의 소들은 각각 2차원 농장의 서로 다른 위치 (x1, y1)...(xN, yN)에 서 있습니다(1 ≤ N ≤ 1,000), 그리고 xi와 yi는 1,000,000 이하의 양의 홀수입니다). 농부 존은 x=a 방정식을 가진 남북 방향의 긴(사실상 무한한 길이의) 울타리를 지어 그의 농장을 분할하고 싶어합니다. (a는 짝수여야 하며, 이는 어떤 소의 위치에도 울타리가 지어지지 않도록 보장합니다). 또한 그는 y=b 방정식을 가진 동서 방향의 긴(사실상 무한한 길이의) 울타리를 짓고 싶어합니다. 여기서 b도 짝수입니다. 이 두 울타리는 점 (a,b)에서 교차하며, 함께 그의 농장을 네 개의 영역으로 나눕니다.
농부 존은 네 개의 영역에 있는 소들이 적절하게 "균형"을 이루도록, 즉 어떤 영역에도 너무 많은 소가 포함되지 않도록 a와 b를 선택하고 싶습니다. M을 네 영역 중 하나에 있는 소의 최대 수라고 할 때, 농부 존은 M을 가능한 한 작게 만들고 싶습니다. M의 가능한 최솟값을 결정하는 것을 도와주세요.
입력
입력의 첫 줄에는 하나의 정수 N이 주어집니다. 다음 N개의 줄에는 각각 한 마리의 소의 위치가 주어지며, x와 y 좌표가 명시됩니다.
출력
농부 존이 울타리를 최적으로 배치했을 때 얻을 수 있는 M의 최솟값을 출력해야 합니다.
풀이
처음에는 이분 탐색으로 접근했다. 소들의 위치를 x축 기준으로 정렬한 배열과 y축 기준으로 정렬한 배열을 두고, 먼저 소들을 둘로 나눌 수 있는 x=a를 찾는다. 다음으로 양쪽 소를 모든 y=b에 대해 나눠보아 가장 작은 M을 찾을 수 있지 않을까? 하지만 최적해의 x=a가 소들을 좌우로 균일하게 나누지 않을 수도 있다. 따라서 이분 탐색만으로는 최적해 여부를 판단할 수 없으므로 탐색 범위를 어떻게 변경해야 할지 결정할 수 없다.
존재하는 모든 좌표를 2차원 배열로 관리(좌표가 정수이기 때문에 표현은 가능하다.)하면 어떤 점을 기준으로 네 구역을 나눠 M을 구할 수 있지 않을까? 물론 직접 세어서. x와 y의 범위가 100만이다. 소의 위치로 가능한 좌표의 수가 너무 많기 때문에 시간 내에 탐색이 불가능하다.
하지만 좌표를 배열로 관리하는 아이디어를 계속 유지하기로 했다. 가능한 좌표 범위는 매우 크지만 이 문제에서 주어지는 소의 최대 수는 1000마리이다. 따라서 x, y좌표 모두 최대 1000가지의 위치만 사용하게 된다. 여기서 사용하는 위치만 오름차순으로 정리해 순서대로 사용하면 모든 좌표를 1000*1000으로 압축할 수 있다.
먼저 소의 좌표를 입력받으며 x좌표와 y좌표의 집합을 생성한다. 모든 소의 좌표를 받았다면 집합을 리스트로 바꾸고 정렬해 각각의 좌표들을 1부터 연속되는 새로운 좌표로 표현한다. 이렇게 되면 모든 좌표를 전부 확인해봐도 시간 내에 문제를 해결할 수 있다.
정답 코드
import sys
input = sys.stdin.readline
def solution():
n = int(input())
cow = [[0] * 1001 for _ in range(1001)]
cor = []
cor_x = set()
cor_y = set()
for _ in range(n):
x, y = map(int, input().split())
cor_x.add(x)
cor_y.add(y)
cor.append((x, y))
cor_x = sorted(list(cor_x))
cor_y = sorted(list(cor_y))
corzip_x = dict()
corzip_y = dict()
k = 1
for X in cor_x:
corzip_x[X] = k
k += 1
k = 1
for Y in cor_y:
corzip_y[Y] = k
k += 1
for x, y in cor:
cow[corzip_x[x]][corzip_y[y]] += 1
for i in range(1001):
for j in range(1, 1001):
cow[i][j] += cow[i][j - 1]
for i in range(1001):
for j in range(1, 1001):
cow[j][i] += cow[j - 1][i]
result = 1000
for i in range(1001):
for j in range(1001):
h = cow[-1][j] - cow[i][j]
v = cow[i][-1] - cow[i][j]
o = n - h - v - cow[i][j]
result = min(result, max(h, v, o, cow[i][j]))
print(result)
solution()
