BOJ 4230 - 사랑과 전쟁

아니 테스트 케이스 while 문 까먹고 안돌려서 계속틀렸다.

$4N$개의 노드를 쓰는 풀이Permalink

2-SAT 문제이고, $2N$개의 노드만 써서 풀 수도 있고, 난 $4N$개를 썼다.

$k$번 신랑이 보람이쪽에 앉는 경우 $=$ $4k$

$k$번 신랑이 철승이쪽에 앉는 경우 $=$ $4k+1$

$k$번 신부가 보람이쪽에 앉는 경우 $=$ $4k+2$

$k$번 신부가 철승이쪽에 앉는 경우 $=$ $4k+2$

일단 $4k$와 $4k+2$는 모두 $\oplus$해준다.

$2$(보람이) 는 무조건 참으로 만들어준다.

이후에 불륜 관계들은 모두 $\lor$ 해주면 된다.

$2N$개의 노드를 쓰는 풀이Permalink

$k$번 신랑이 보람이쪽에 있는 경우 = $2k$

$k$번 신부가 보람이쪽에 있는 경우 = $2k+1$ 로 둔다.

이 경우에 $1$(보람이가 보람이 방향에 있는 경우)를 항상 참으로 만들어주고, $(\lnot x_0)$

불륜 관계들에 대해서 $u$번 신랑과 $v$번 신부라면 $2u$가 참(보람이 방향에 앉기)이거나 $2v+1$ 이 참이여야 하므로 $(2u \lor 2v+1)$ 절을 추가해준다.

이후 2-SAT을 돌리고, $i$ 번째 값이 $1$이라면 신부가 보람이쪽에 앉아있다는 것이므로 $kw$를, 아니라면 $kh$를 출력한다.