1043 거짓말

• quickn님의 풀이를 통해서 이해한 내용을 바탕으로 작성하였습니다.

모든 사람들은 진실을 알고 있거나 진실을 모르고 있습니다. 즉, 최종 상태에서 사람들의 집합 P는 서로소인 두 부분집합 K와 K'로 나눠집니다. (전자가 진실을 아는 사람, 후자는 그 반대)

초기 상태는 K = K0, K' = {}이므로 파티를 검사하면서 K와 K'를 갱신해 나가야 합니다.

파티 하나를 지날 때마다 다음과 같은 세 가지 상황을 마주칠 수 있습니다.

1. 모든 파티 참가자가 진실을 몰라도 됨 (파티 참가자와 K가 서로소)

이 경우는 K' = K' ∪ P로 진행할 수 있습니다.

2. 모든 파티 참가자가 진실을 알아도 됨 (파티 참가자와 K'가 서로소)

이 경우 K = K ∪ P로 진행할 수 있습니다.

3. 나머지 경우

진실을 듣는 사람과 거짓말을 듣는 사람이 같은 파티에 있는 경우는 존재하지 말아야 하는 상황입니다.

사람들의 집합 P는 반드시 K와 K'로 나뉨이 보장되어 있으므로, 1번과 2번 선택지를 각각 따라갔을 때의 결과를 저장해 최대 거짓말 횟수를 산출할 수 있습니다.