[PS] 2014 Daejeon 6895 Deduction

Deduction 의 뜻은 추론 이라는 뜻이다.

초반 설명이 이해하기 어렵지만 간략하게 요약하면 다음과 같다.

  • TYPE1 은 무조건 참이다.

  • TYPE2 는 [a,b,c...] -> false , 즉 a,b,c...중 적어도 하나는 거짓이라는 뜻이다.

  • TYPE3 는 [a,b,c...] 가 모두 참이면 그에 상응하는 결과도 참이다.

6 2 0 5
1
2
1 1 6
1 2 6
2 1 6 3
2 2 4 1
2 5 6 2

맨 첫줄 6 2 0 5 는 n, m1,m2,m3 이다.

n은 사용할 숫자의 개수이다 여기선 1,2,3,4,5,6 이 사용된다.

2는 m1의 개수 0 은 m2의 개수 5는 m3의 개수이다.

본 문제는 모든 줄이 참이되면 YES 그렇지않고 모순이 있으면 NO를 출력한다.

1과 2는 참이다. TYPE1에 의거

TYPE2는 본 예시에서는 없다.

1 1 6 라인에서 첫번쨰 1은 벡터의 수이다. 6은 TYPE3의 결과이고

벡터의 수가 1개니 1->6 이된다. 즉 1이 참이면 6도 참이라는 뜻이다.

1이 참이니 6도 참이다.

1 2 6 에서는 2->6 인데 2가 참이니 6은 역시 참이다.

2 1 6 3 에서 는 벡터의 수가 2개이니 [1,6]->3이다. 1,2,6이 현재 참이니 3도 참이된다.

[2,4]->1 인데 우리가 1,2,6이 참인걸 알고있다. 4는 아직 참인지 거짓인지 모른다.

이 수식이 성립할려면 4는 참이여야한다.

[5,6]->2 에서도 2와 6은 참이므로 5도 참이여야한다.

모든 수식이 참이므로 본 예시의 답은 YES이다.

원리는 간단하다. 본 문제는 boolean 배열을 만들고, 모두 false 로 초기화 한다음 시작한다.

TYPE1에 있는것들을 true로 설정한다음,

TYPE3를 통해 참이될수 있는값들을 결정한다.

그후 TYPE2를 모두 검사해 식이 참인지 거짓인지를 판별하면 된다.