2-SAT 썸네일형 리스트형 BOJ)15675 괴도 강산 문제 :icpc.me/15675 모든 보석을 집고, 위치 추적기를 하나도 안 가진 상태가 가능하다면 1을 아니면 0을 출력하는 문제이다. 문제의 조건을 잘 읽어보면 2NF로 모델링이 가능하여 2-SAT을 이용한 풀이가 가능하다. 우선 보석을 고르는 조건은, 보석이 존재하는 행을 a 열을 b라고 하였을 때, a b 중에 하나밖에 선택되지 않으므로 (a&&!b)||(!a&&b) 라는 식이 세워진다. 하지만 이는 CNF가 아니므로 식을 잘 풀어내어 (a||b)&&(!a||!b)로 변형하여 추가해준다. 다음으로 위치추적기를 밟는 경우 다시 그자리에 돌려놔야 하므로 a b 를 모두 선택하거나 a b를 모두 선택하지 않는 경우 중 한 경우가 이루어져야 한다. 즉(a&&b)||(!a&&!b) 라는 식이 세워지고 이를.. 더보기 BOJ)7535 A Bug's Life 문제: icpc.me/7535 서로 성별이 다른 두 벌레들의 정보가 주어질 때 vaild한지 여부를 묻는 문제이다. 우리는 두 벌레들의 정보가 들어온다는 걸 이용하여 2-SAT 모델링을 통하여 문제를 해결 할 수 있다. A와 B가 들어 왔을 때 두 벌레의 성별이 다르다는 걸 (A||B)&&(!A||!B)로 표현해준 뒤 이를 이용하여 2-SAT 모델링을 한 뒤 vaild 여부를 판단해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include #include #include #include #include .. 더보기 BOJ)3747 완벽한 선거! 문제: icpc.me/3747 문제에서 A||B의 셋이 M개가 주어지고 M개의 모든 셋이 동시에 참이 될 수 있는 지 여부를 묻는 문제이므로 2-SAT 모델링을 통해 문제를 해결할 수 있다. 주어진 조건대로 간선을 연결해준 뒤 2-SAT 모델링을 통하여 참 여부를 판단하여 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include #include #include #include #include using namespace std;struct TwoSAT { int n, c, sccc; vec.. 더보기 이전 1 다음