boj, 백준) 2-SAT - 1
1. 문제 링크 www.acmicpc.net/problem/11277 11277번: 2-SAT - 1 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 20)과 절의 개수 M (1 ≤ M ≤ 100)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 양수인 www.acmicpc.net 2. 문제 개요 2-SAT를 풀어보자. SAT에 대한 설명은 본문에 잘 나와있다. 3. 문제 힌트 N은 최대 20, M은 최대 100, 전수조사로 충분히 풀 수 있는 크기이다. 시간 복잡도는 모든 경우의 수 (2^20)에 대해 M개의 식을 검증하면 된다. O(2^(N)*M)인데 간당간당.. 4. 문제 풀이 dfs방식으로 모든 순열을 만들어..
boj, 백준) 2966. 찍기 (C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/2966 2966번: 찍기 문제 상근이, 창영이, 현진이는 역사와 전통을 자랑하는 Sogang ACM-ICPC Team에 가입하려고 한다. 하지만, 가입하려고 하는 모든 지원자는 C언어 필기시험을 통과해야 한다. 이들은 C언어를 할 줄 모른다. 따라서, 필기시험을 모두 찍으려고 한다. 상근이는 A, B, C, A, B, C, A, B, C, A, B, C, ...와 같이 찍어야 통과할 수 있다고 생각한다. 하지만, 창영이는 B, A, B, C, B, A, B, C, B, A, B www.acmicpc.net 2. 문제 개요 상근이는 A B C A B C A B C... 창영이는 B A B C B A B C B... 현진이는 C C ..