문제 https://www.acmicpc.net/problem/16915 16915번: 호텔 관리 첫째 줄에 방의 개수 N(2 ≤ N ≤ 100,000)과 스위치의 개수 M(2 ≤ M ≤ 100,000)이 주어진다. 둘째 줄에는 초기 방의 잠금 상태가 1번 방부터 순서대로 주어진다. 0은 닫힌 상태, 1은 열린 상태이다. 셋째 www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 2-SAT 문제에 대하여 모른다면 반드시 먼저 공부하고 옵시다. [2-SAT] 2 - Satisfiability Problem / 충족 가능성 문제 (알고스팟 회의실 배정 풀이) 이번 문제는 (A || B) &&(B || C) && (C || D) 와 같은 논리곱 정규형(Conjunctive normal..

문제 https://www.acmicpc.net/problem/3648 3648번: 아이돌 각 테스트 케이스에 대해서, 상근이를 포함해, 다음 라운드 진출 목록을 심사위원의 의심 없이 만들 수 있으면 'yes'를, 없으면 'no'를 출력한다. www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 2-SAT 문제에 대하여 모른다면 반드시 먼저 공부하고 오자. [2-SAT] 2 - Satisfiability Problem / 충족 가능성 문제 (알고스팟 회의실 배정 풀이) 이번 문제도 심사위원의 투표 A와 B중 하나는 반드시 영향이 있어야 하기 때문에 두 가지 변수로 절을 생성할 수 있는 2-SAT 문제이다. 각 절은 (A || B) 로 표현된다. 심사위원들의 투표를 토대로 함의 그..

문제 https://www.acmicpc.net/problem/11281 11281번: 2-SAT - 4 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 10,000)과 절의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 일단 2-SAT에 대하여 공부하고 문제를 풀어봅시다. [2-SAT] 2 - Satisfiability Problem / 충족 가능성 문제 (알고스팟 회의실 배정 풀이) 이전 문제에 해당하는 [백준] 2 - SAT - 3(11280) 문제를 먼저 해결하고 옵시다. 이번 문제에서 위..

문제 https://www.acmicpc.net/problem/11280 11280번: 2-SAT - 3 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 10,000)과 절의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 일단 2-SAT에 대하여 공부하고 문제를 풀어봅시다. [2-SAT] 2 - Satisfiability Problem / 충족 가능성 문제 (알고스팟 회의실 배정 풀이) 이번 문제에서 위의 2-SAT 해설과 다른 점이 있다면 두가지 변수가 or로 연결된 절(clause)이 직접 주..