mojo's Blog

문제 링크 => 3648번: 아이돌 (acmicpc.net) 3648번: 아이돌 각 테스트 케이스에 대해서, 상근이를 포함해, 다음 라운드 진출 목록을 심사위원의 의심 없이 만들 수 있으면 'yes'를, 없으면 'no'를 출력한다. www.acmicpc.net 2-SAT 문제이다. 각 심사위원은 자신이 행사한 두 표 중 적어도 하나는 결과에 영향을 미쳐야 한다고 생각을 한다. 두 표 모두와 반대되는 결과가 나오면, 심사위원은 투표 결과에 대해서 의심을 하게 된다. 즉, 두 표 모두와 반대되는 결과가 나오면 투표 결과에 대해서 의심을 하게 되는데 이를 방지해야 한다. 예를 들어서 심사위원 X 가 1번째 참가자(A) 에게 찬성, 2번째 참가자(B) 에게 반대를 던졌다고 하자. 그렇다면 f(A, B) = A ..

문제 링크 => 16367번: TV Show Game (acmicpc.net) 16367번: TV Show Game Your program is to read from standard input. The input starts with a line containing two integers, k and n (3 < k ≤ 5,000, 1 ≤ n ≤ 10,000), where k is the number of lamps and n the number of game participants. Each of the following n lines contains t www.acmicpc.net SCC 를 활용한 2-SAT 문제이다. 이 문제는 3개중에 2개를 만족하도록 세워야 하는게 핵심이다. a, b, c가 ..

문제 링크 => 2207번: 가위바위보 (acmicpc.net) 2207번: 가위바위보 첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각각의 학생들의 선택을 나타내는 두 정수 x, y(1≤|x|, |y|≤M)이 주어진다. x가 양수일 경우에는 원장선생님이 x번째에 가위를 낼 거라는 의 www.acmicpc.net SCC를 활용한 2-SAT 문제이다. 이 문제의 핵심은 학생들은 가위, 바위만 낼 수 있고 학생이 i 번째와 j 번째에 가위, 바위 둘중에 하나를 랜덤으로 선택할 때 둘중 하나는 무조건 맞아야 한다. 이때, i 번째에 예상하는 것을 xi, j 번째에 예상하는 것을 xj 라고 할 때, (xi v xj) 가 True 이기 위해서 ~xi -> xj 또는 ~xj -> xi 가 True 임..

문제 링크 => 11281번: 2-SAT - 4 (acmicpc.net) 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 SCC를 활용한 2-SAT 문제이다. 이 문제는 2-SAT - 3 에서 출력해야 할 것이 추가되었다. x1, x2, x3, ..., xn 의 true / false 를 임의로 설정해서 출력하도록 해줘야 한다. 2-SAT - 3 에서 만들었던 코드에서 inDegree 를 추가하여 xi, ~xi 의 진입차수를 비교하여 답을 내는것이..

문제 링크 => 11280번: 2-SAT - 3 (acmicpc.net) 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 SCC 를 활용하는 문제이다. 여기서 기본으로 알아야 할 상식은 다음과 같다. 1. ~a v b 는 a -> b 또는 ~b -> ~a (대우) 로 표현이 가능하다. 2. SCC로 묶인 xi, ~xi (i = 1, 2, 3, ... , n) 에 대하여 i가 동일할 경우 xi, ~xi 가 동시에 있는 경우 무조건 False 이다. ..