BOJ 1200 - 기상예측

BOJ 1200 - 기상예측

모든 가로칸을 나눠본다. $s < m \le 18$ 이기 때문에 최대로 커도 $_{17}C_8$ 정도밖에 경우의 수가 안나온다.

그럼이제 세로칸에 대해 $r$ 개로 최대한 적게 분리할 수 있는 것을 이분탐색으로 찾아주면 된다.

시간복잡도는 $O\left( \dbinom{m}{m/2} \cdot \log_2 M \cdot n \right)$ 정도가 걸린다.