ez_code   4년 전

문제

참가자가 제한 시간 안에 최대한 많은 3-SAT 문제를 푸는 3-SAT 문제 대회가 돌아왔습니다. 3-SAT 문제는 대표적인 NP 문제로, 불 논리식이 각 절이 정확히 세 개의 리터럴로 이루어진 논리곱 표준형으로 주어집니다. 각 리터럴은 참 또는 거짓을 값으로 갖는 변수를 긍정하거나 부정함으로써 형성됩니다. 모든 절이 참이 되도록 변수를 설정할 수 있는지 여부를 판단하는 것이 문제입니다. 그 어떤 절도 똑같은 리터럴을 중복해 포함하지는 않습니다 (다만 절이 ¬xi와 xi를 동시에 포함할 수는 있습니다). 아래는 3-충족 가능성 문제의 예시입니다 (샘플 입력 1이기도 합니다.):

(¬x1 ∨ x2 ∨ x3) ∧ (¬x1 ∨ ¬x2 ∨ x3) ∧ (x1 ∨ ¬x2 ∨ x3) ∧ (x1 ∨ ¬x2 ∨ ¬x3) ∧ (x1 ∨ x2 ∨ ¬x3)

오이빈드는 대회의 심판으로, 대회가 시작하기 전 다른 심판이 만든 문제의 질을 검사할 책임이 있습니다. 오이빈드는 절이 8개 미만인 3-SAT 문제를 싫어합니다 - 대회 참가자에게 큰 어려움이 되지 않기 때문입니다. 그러므로 그는 이러한 문제에 만족하지 못할 것입니다. 오이빈드는 절이 8개 이상인 문제는 문제의 답을 구하는 것이 어려움을 알고 있으므로 - 이러한 문제에는 만족할 것입니다. 3-SAT 문제의 예시가 주어질 때, 오이빈드가 어떤 판단을 할지 찾아줄 수 있나요?

입력

 입력은 3-SAT 문제의 예시입니다. 첫 줄에는 공백으로 나뉜 두 정수가 들어옵니다: 절의 수를 나타내는 m (1 <= m <= 20)과 변수의 수를 나타내는 n (3 <= n <= 20)입니다. 그리고 m개의 절이 줄마다 하나 입력됩니다. 각 절은 공백으로 나누어진 [-n, n] \ {0} 범위의 3개의 정수로 구성됩니다. 각 절에서, 세 정수는 절의 세 리터럴에 대응됩니다. 만약 리터럴 값이 음수이면 상응하는 변수가 거짓일 때 참이 됨을 의미하며, 양수이면 상응하는 변수가 참일 때 참이 됨을 의미합니다.

출력

만약 오이빈드가 3-SAT 문제 예시에 만족하면 "satisfactory"를, 아니면 "unsatisfactory"를 출력합니다.

thesmartist   4년 전

입력 문단의 positive, negative는 '긍정형', '부정형' 보다는 '양수', '음수'가 적절할 것 같습니다.
입력이 양수 k가 들어오면 리터럴 xk가 참이고, 음수 -k가 들어오면 리터럴 xk가 거짓이라는 뜻입니다.
사실 어려운 척하는 국어 문제라 큰 의미는 없습니다

ez_code   4년 전

지문 positively/negatively 해석을 그대로 썼던 것 같습니다.

감사합니다, 수정했습니다 :)

eric00513   4년 전

큰 상관이 있는 것은 아니지만 보통 3-SAT이라고 짧게 부르는 것 같은데, 3-SAT으로 바꿔주실 수 있을까요?

댓글을 작성하려면 로그인해야 합니다.