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
이전 반에 들어가면 안되므로
이전 반에 안들어가게 절을 하나 만들어준다.
그리고 남은 두반은 ⊕로 절을 만들어준다.
이제 이분탐색으로 찾는데, m번 초과의 순서를 가진 친구들과 같은 반이 안되게끔 해야한다.
¬(x0∧y0)∧¬(x1∧y1)∧¬(x2∧y2)
를 드모르간 법칙으로 풀면 CNF가 나와서 그대로 써주면 된다.
Comments