반응형
[ Contents ]
1. 문제 (링크 참조)
17903번: Counting Clauses
The input is a single instance of the 3-SAT problem. The first line is two space-separated integers: m (1 ≤ m ≤ 20), the number of clauses and n (3 ≤ n ≤ 20), the number of variables. Then m clauses follow, one clause per line. Each clause consists
www.acmicpc.net
2. 문제 풀이
3항인 SAT(Satisfiability problem, 충족 가능성 문제)입니다. 즉, 해당 논리식이 참이 되는 변수값이 존재하는지를 찾는 문제입니다. 해당 문제는 NP-완전문제로, 복잡도가 상당히 높은 문제입니다.
당연히 NP-완전을 해결하라는 문제는 아니죠.
다음과 같은 순서로 x1, x2, x3의 입력이 주어집니다. x1, x2, x3의 부호 조합은 총 8가지입니다.
(+, +, +), (-,+,+), ...
그러므로 입력 절이 8개 이상이 되면, 무조건 참이 되는 충족조건을 알 수 있습니다.
3. 코드
# 입력
m, n = map(int, input().split())
print("satisfactory" if m >= 8 else "unsatisfactory")
반응형
'Algorithm' 카테고리의 다른 글
| [구현/수학] 백준 21631 Checkers - 파이썬(Python) (0) | 2022.10.16 |
|---|---|
| [수학/브루트포스] 백준 3276 ICONS - 파이썬(Python) (0) | 2022.10.15 |
| [구현/수학] 백준 21354 Äpplen och päron - 파이썬(Python) (0) | 2022.10.13 |
| [구현/브루트포스] 백준 17614 369 - 파이썬(Python) (0) | 2022.10.12 |
| [구현/수학] 백준 24751 Betting - 파이썬(Python) (0) | 2022.10.11 |
댓글