BOJ 5009 - 유치원
2-SAT 문제이다.
일단 노드 번호는 다음과 같다.
- $6k+0$ $k$번 학생이 $0$번 반 배정
- $6k+1$ $k$번 학생이 $0$번 반 배정 X
- $6k+2$ $k$번 학생이 $1$번 반 배정
- $6k+3$ $k$번 학생이 $1$번 반 배정 X
- $6k+4$ $k$번 학생이 $2$번 반 배정
- $6k+5$ $k$번 학생이 $2$번 반 배정 X
이전 반에 들어가면 안되므로
이전 반에 안들어가게 절을 하나 만들어준다.
그리고 남은 두반은 $\oplus$로 절을 만들어준다.
이제 이분탐색으로 찾는데, $m$번 초과의 순서를 가진 친구들과 같은 반이 안되게끔 해야한다.
$$
\lnot(x_0 \land y_0) \land \lnot(x_1 \land y_1) \land \lnot(x_2 \land y_2)
$$
를 드모르간 법칙으로 풀면 CNF가 나와서 그대로 써주면 된다.
Comments