[백준/Python] 1813번 : 논리학 교수

https://www.acmicpc.net/problem/1813

문제 해석 및 접근

"정확하게 0개의 말은 참이다"

"정확하게 1개의 말은 참이다"

"정확하게 2개의 말은 참이다"

이런 3개의 문장이 칠판 위에 쓰여져 있고, 이 문장들 중 몇 개의 문장이 참인지 가려내야 한다.

천천히 접근해서, '(칠판에 쓰여진) 0개의 말이 참이다' 라는 문장이 True라면, 이 문장을 포함한 칠판에 있는 모든 문장은 거짓이어야 한다.  여기에서 모순이 발생한다. 자신이 True인 것에서 참인 문장이 1개가 고정되는데, 문장 자신이 말하는 말은 거짓이 된다.

즉 '0개의 말이 참이다' 라는 문장은 거짓말쟁이 문장이고, 모순이다. 즉, '0개의 말이 참이다' 라는 문장은 0개 존재해야 한다. 

 

반면 '정확하게 2개의 말이 참이다' 라는 문장이 True라고 가정해보자. 칠판 위에는 3개의 문장이 있고, 이 문장을 포함한 2개는 '참'이어야 한다. 즉 '0개의 말이 참이다' '1개의 말이 참이다' 라는 문장 2개 중 하나만 True임을 나타내면 된다.

 

'정확하게 0개의 말이 참이다' 라는 문장은, 위에서 봤듯이 항상 거짓을 말하는 문장이다. 그렇다면 '정확하게 1개의 말이 참이다' 라는 문장이 True 일 수 있을까?

그럴 수 없다. 만약 '정확하게 1개의 말이 참이다'라는 문장이 True라면, 칠판에 쓰여진 3개의 문장 중 하나만 True여야 하는데 우리는 이미 전제에서 '정확하게 2개의 말이 참이다' 라는 문장이  True라고 못 박았기 때문이다. 즉 '1개의 말이 참이다' 라는 문장은 거짓이고, 2개의 문장이 모두 거짓이었다. 즉, '정확하게 2개의 말이 참이다' 라는 문장도 거짓인 것이다.

 

반면 '정확하게 1개의 문장이 참이다' 라는 문장은 참일 수 있다. 왜냐하면, 문장 자기 자신이 True라고 가정해도, 남은 두 문장의 T/F 여부가 '1개 문장이 참이다' 라는 자신의 진위여부에 영향을 미치지 않기 때문이다. 즉, 1개의 말이 참이다 라는 문장은 1개 존재해야 한다. 

예시를 바꿔서, '정확하게 2개의 말이 참이다' 라는 문장을 '정확하게 1개의 말이 참이다' 라는 문장으로 바꿔보겠다. 칠판에는, '0개의 말이 참이다' '1개의 말이 참이다' '1개의 말이 참이다' 라는 문장 3개가 쓰여져 있다.

 

이 경우에는, 답이 몇개가 될까? '정확하게 1개의 말이 참이다' 라는 문장이 참이라면, 다른 '1개의 말이 참이다'라는 문장도 참이 되어야 한다. 하지만, 이렇게 되면 칠판에는 참이 되는 문장이 2개가 되어 버린다. 즉, 이때의 답은 존재하지 않는다.

하지만 답이 존재하지 않을 뿐, 모순과는 다르다. 예제4를 보면 알 수 있다.

 

알고리즘

예제와 위 글을 대충 읽으면 감이 올 것이다. 프로그래밍으로 구현하는 방법은

'정확하게 i개의 문장이 참이다' 라는 문장이 i개 존재한다면, 그 문장 i개는 모두 참이다. 

하지만 칠판에 '0개의 문장이 참이다' 라는 문장이 존재하고 답이 존재하지 않을 경우, 이 경우에는 모순이 된다.

즉, 모순을 판별하는 방법은 , 답이 없는데, '0개의 문장이 참이다' 라는 문장이 존재할 경우를 가려내면 된다.

 

코드

input = __import__('sys').stdin.readline

n = int(input())

s = list(map(int,input().split()))

d = dict()

for elem in s:

    if (elem not in d.keys()):

        d[elem] = 1

    else: d[elem] += 1

ans = 0

d = dict(sorted(d.items(),key=lambda x:(-x[0],x[1])))

for k,v in d.items():

    if (k == v):

        ans = k

        break

if (ans == 0 and 0 in d):

    print(-1)

else:

    print(ans)    

문장이 나온 횟수를 세기 위해, dictionary를 이용해 value에 나온 횟수를 입력했다.

조금 다른 점이 있다면, dictionary에서 key가 큰 순서대로 sort하고 싶어서 lambda 함수를 조정했다.