BOJ 28276 - Yawned-Zoned
이분탐색을 이용해서 풀 수 있다.
$M$ 이하의 그룹만 만들게 하기위해 필요한 칸막이의 개수를 $f(M)$ 이라 하면 $f(M) \le W$ 를 만족하는 가장 큰 $M$이 정답이다.
이를 해결하는 방법은 DSU로 일단 한 칸씩 오른쪽으로 밀면서 $1$ 인 칸들끼리 모두 merge 해봐서 크기를 보는 것이다.
만약 집합중 크기가 $M$ 초과가 나온다면 해당 시도에서 merge된 것들을 모두 roll-back 시키면 된다.
DSU에서의 롤백은 스택을 이용하여 히스토리를 관리한다.
시간복잡도 $O(M \cdot RC)$ 로 풀 수 있다.
Comments