백준 Load Balancing (Silver) 11997 - C++
https://www.acmicpc.net/problem/11997
11997번: Load Balancing (Silver)
Farmer John's \(N\) cows are each standing at distinct locations \((x_1, y_1) \ldots (x_N, y_N)\) on his two-dimensional farm (\(1 \leq N \leq 1000\), and the \(x_i\)'s and \(y_i\)'s are positive odd integers of size at most \(1,000,000\)). FJ wants to par
www.acmicpc.net
일단 문제 설명이 영문으로 되어있어서 다들 많이 풀지도 않고, 인기 없는 문제.
신촌 알고리즘 캠프 도중 좌표 압축의 연습문제로 주어져서 풀게 됐다.
입력으로는 소들의 위치인 2차원 좌표들이 N개 들어오고,
해당 2차원을 수직선 하나, 수평선 하나로 나누어 각 나눠진 평면들에 소의 수, 4가지를 구해서 그중 최대를 구한다.
모든 경우에서의 최대값 중 최솟값을 찾는다.
1 <= N <= 1,000 이고, 소들의 위치의 최대 최소는 10^6이다.
<접근 방식>
10^6 모두를 검사하기에는 시간이 너무 오래 걸린다.
마침 N이 1000 정도의 값이고, 개별 값의 크기가 중요한 게 아니라, 값 사이의 상대적인 크기만 의미가 있으므로,
좌표 압축을 적용하면 1000X1000 크기에서 해결할 수 있을 거라고 생각했다.
해서 모든 경우에 적용하려고 하니, 매번 계산하는데 다시 O(n)이 들어서 O(n^3)으로 1초의 시간제한을 통과하지 못했다. 시간을 더 줄일 방법이 뭐가 있을까 생각했는데, 어차피 소들의 좌표는 고정이니, 미리 좌표마다의 값을 구해두면 O(1) 정도의 시간에 하나의 경우를 검사할 수 있겠다.라는 생각이 들어, Presum을 이용해서 해결했다.