티스토리 뷰

ICPC/2014 대전

B. Deduction

전명우 2014.11.09 13:40

$N$개의 명제 $S_1, S_2, ..., S_N$이 있고, 명제들 사이의 관계가 주어졌을 때 모순의 여부를 판별하는 문제다.


명제는 참 또는 거짓일 수 있으며, 우리는 어떤 명제 $S_i$에 대해 참이라고 확신하거나, 참인지 거짓인지 모르는 경우 두 가지 상황이 있다. 관계는 세 가지 종류로 주어진다. 이 종류를 자세히 살펴보면 우리는 명제가 참인지 거짓인지 모를 때, 거짓이라고 가정해도 모순 판별 여부에 아무런 영향이 없음을 알 수 있다. 쉽게 말하자면, 참이라는 확신이 없을 때에는 거짓이라고 생각해도 무관하다.


위와 같은 사실을 알았을 때, 우리는 1번 종류와 3번 종류 관계를 잘 이용해서 참이라고 확신할 수 있는 명제들을 추려내면 된다. 참이라고 확신할 수 있는 명제들을 추려낸 뒤, 2번 종류 관계에서 모순이 있는지 확인하면 문제가 해결 된다. 총 시간복잡도는 $O(N^2)$ 이다.


코드 보기

'ICPC > 2014 대전' 카테고리의 다른 글

G. Road Repair  (0) 2014.11.10
F. Permutation Cycles  (0) 2014.11.09
E. Marbles  (0) 2014.11.09
D. Exploration  (2) 2014.11.09
C. Eureka Theorem  (0) 2014.11.09
B. Deduction  (0) 2014.11.09
댓글
댓글쓰기 폼