https://www.acmicpc.net/problem/31676
문제 요약
- 두 종류 증언이 있음 : S중에 범인이 있다. S중에 범인이 없다
- N 명중 한 명이 범인이라고 하면
- 범인이 증언한 것은 거짓. 나머지는 참
- 그리고 모든 증언에 모순이 있으면 안됨
- 모순이 아니다 = 모든 증언에서 그 한명이 범인이라고 되어있으면 됨
- 이 조건을 만족하면 그 한명이 범인일 가능성이 있음
- N=10만, 증언에 등장하는 학생 20만
- 범인이 될 수 있는 번호 출력. 없으면 특정 문자열 출력
접근법
- 일단 문제는 이해하기가 쉽지는 않음
- 아무튼 어떤 한 명을 범인이라고 가정하고
- S 중에 범인이 있다에 그 한명이 있거나
- S 중에 범인이 없다에 그 한명이 없으면 됨
- 그리고 범인이 한 증언은 뒤집어서 생각하면 됨 -> 범인이 있다<->없다
- 비슷한 문제인 "특별한 케이크(easy)"에서는 완전 탐색으로 접근했음
- 1 ~ N 까지 범인이라고 가정하고, 증언에 대입해서 맞는지 틀리는지 판단
- 근데 이 문제는 일단 N이 10만이라 완전탐색을 하면 N^2 시간이 걸림
- 특정 한 명(=X라고 부르면)이 범인 상황을 관찰해보면
- X외에 다른 사람들은 X를 범인이라고 지칭할 것임
- 범인이 없다라고 증언한 것도 뒤집으면 다른 쪽에 범인이 있다로 이해할 수 있음
- X의 증언을 뒤집어서 생각하고 그 증언에 X가 범인이라고 지칭할 것임
- 결국 모든 증언에서 X를 지칭 = X를 지칭한 건수가 N개
- 단 X의 증언은 뒤집은 상태이므로 실제로는 지칭한 건수가 N-1개여야함
- 정리하면 X를 지칭한 건수가 N-1개이고, X 자신은 X를 지칭하지 않으면 X가 범인일 수 있음
구현 - 범인으로 지칭한 카운트
- S 중에 범인이 있다
- 그대로 세면 됨
- S 중에 범인이 없다
- S에 안 들어가는 사람을 범인으로 지칭해서 세면됨
- 근데 이렇게 세면 문제가 있음 : 시간 복잡도
- S에 안들어가는 사람이 최대 N명이게 되면 N*N만큼 카운팅을 하게됨
- ex) 매 증언마다 size(S) = 1이면, N-1만큼 카운팅을 하게 됨
- 범인이 없다라고 지목된 사람외에는 모두 범인으로 지목됨을 응용하면 되는데
- 예를 들어보자
- S 중에 범인이 없다라는 증언이 5번 있었다고 보고
- 그 중에 4번 사람이 2번 지목되었다고 보자
- 4번 사람은 나머지 3번에서는 지목이 안됨 = 범인으로 지목되었을 것임
- 즉 범인이 없다라는 증언 전체 회수 - K 번사람이 범인이 없다라고 증언된 회수 = 범인으로 카운팅 해야하는 개수
- 따라서 전체 범인으로 지목된 회수 = 범인이 있다라고 증언된 회수 + 위의 값
구현 - 스스로를 지칭하는 경우
- S에 범인이 있다라고 하고 S에 자기 자신이 있는 경우
- S에 범인이 없다라고 하고 S에 자기 자신이 없는 경우
newbieski