문제 링크
- https://icpc.me/15310
사용 알고리즘
- 볼록 껍질
- 분할 정복
시간복잡도
- $O(N^2 \log N)$
- $O(X^{2/3}N \log N)$
풀이
가능한 모든 $N \choose K$가지의 경우에 대해, 2차원 평면에 점 $(\sum W_i, \sum H_i)$를 플로팅하면, $x\times y$가 최소인 점을 구하는 문제로 바뀌게 됩니다.
$x\times y$의 최솟값이 $M$이라는 것은 곡선 $xy=M$이 한 점 $P(x_p, y_p)$을 지나고, 곡선 밑에 존재하는 점이 없다는 것을 의미합니다. $P$는 특정 기울기에서 극단에 있는 점이므로 $\min\left{ ax+by \right} = ax_p+by_p$를 만족하는 실수 $a, b$가 존재합니다. $N \choose K$개의 점들의 볼록 껍질을 구했을 때, 기울기가 $-a/b$인 접선에 접하는 점이 $P$라고 생각하면 이해가 쉬울 것입니다.
적당한 $(a, b)$ 쌍들에 대해 $ax+by$가 최소가 되는 점 $P’(x’, y’)$를 구해서, 모든 $P’$에서 $x’y’$의 최솟값을 구하는 방식으로 접근해 봅시다. $(a, b)$의 후보가 충분히 적다면 이 방식으로 문제를 해결할 수 있을 것입니다. $a, b$가 고정되어 있을 때 $P’$의 좌표를 구하는 것은 $aw_i + bh_i$가 작은 점부터 $K$개를 선택하면 됩니다.
가장 먼저 생각할 수 있는 $(a, b)$ 후보의 상한은 $O(N^2)$입니다. 서로 다른 두 점의 기울기만 고려해도 충분하다는 것은 직관적으로 알 수 있기 때문입니다. 하지만 $O(N^2)$개의 후보를 확인하면 전체 시간 복잡도가 $O(N^3 \log N)$이 되어서 시간 초과를 받게 됩니다. 여기에서 올바른 풀이로 갈 수 있는 두 가지 길이 있습니다. 첫 번째 방법은 각 후보를 확인하는 시간을 줄이는 것, 두 번째 방법은 후보의 개수를 줄이는 것입니다.
첫 번째 방법인 각 후보를 $O(\log N)$ 시간에 확인하는 것부터 알아봅시다. Bulldozer Trick을 사용할 것입니다. 기울기를 오름차순으로 확인하면 매번 인접한 두 원소 한 쌍의 위치만 바뀌기 때문에, 세그먼트 트리 등을 이용해 가장 작은 $K$개의 합을 빠르게 확인할 수 있습니다.
두 번째 방법은 좌표 범위가 $X$일 때 볼록 껍질의 최대 크기는 $O(X^{2/3})$, 평균적으로 $O(X^{1/3})$이라는 사실을 이용하는 것입니다. 볼록 껍질 위의 점들을 빠르게 뽑아낼 수 있다면 $O(X^{2/3}N \log N)$ 정도의 시간에 해결할 수 있습니다.
먼저 기울기가 $1/0, 0/1$인 접선의 접점 $P_1, P_2$를 구합시다. 각각 $O(N \log N)$ 시간에 구할 수 있습니다.
그 다음으로는 $P_1$과 $P_2$를 잇는 선분의 기울기에서의 점점 $P_3$를 구하고, 그 다음은 $P_1, P_3$을 잇는 선분과 $P_2, P_3$을 잇는 선분을 탐색합니다. 이러한 과정을 분할 정복을 이용해 수행할 수 있고, 볼록 껍질의 점의 개수 만큼만 재귀 호출하게 됩니다.
기울기가 주어졌을 때 $O(N \log N)$ 시간에 접점을 구할 수 있으므로, 전체 시간 복잡도는 $O(X^{2/3}N \log N)$입니다.
아래 코드는 두 번째 방법을 구현한 코드입니다.
전체 코드
1 | |