BOJ 1200 - 기상예측

image.png

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

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

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

Tags:

Categories:

Updated:

Comments

You may also enjoy

thumbnail

iOS, SwiftUI Guide (AI generated)

제가 예전에 공부 내역을 정리한 포스팅을 GPT 4.5 Deep Research로 내용을 정리해달라 한 문서입니다.