COCI 2014/2015 contest1 4- 마피아(MAFIJA) > 문제은행 : 정보올림피아드&알고리즘




2868 : 마피아(MAFIJA)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
24 회   
시도횟수
162 회   

문제

마피아 게임은 잘 알려진 게임이다. 정올 캠프를 비롯하여 학생들이 캠프에 갔을 때 늦은 밤 모여 앉아 하는 게임 중 하나이기도 하다. ^^

 

이 문제를 풀기 위하여 마피아 게임의 규칙을 모두 알 필요는 없다. 단지 마피아는 누가 누구인지 모두 알고 평민은 누가 누구인지 전혀 모른다는 것만 알면 된다. 또한 마피아는 게임을 하는 동안 자신이 평민인척 한다.

 

게임이 진행 중 인데 현재 N명이 남아 있고 각 사람이 어느 한 사람만을 지목하여 마피아라고 말할 수 있다. 그런데 평민은 추측하여 지목하는 것이고 마피아는 평민인 척 하면서 평민을 마피아로 지목한다. 마피아는 마피아를 지목하는 일이 없고 평민은 누구든 지목할 수 있다. 어느 한 사람이 여러 번 지목될 수 있다.

 

마피아가 누구인지는 모르지만 마피아로 지목된 사람에 대한 정보를 알고 있다고 할 때, 현재 남은 N명의 사람중에서 마피아는 최대 몇 명으로 추측 할 수 있는지 구하는 프로그램을 작성하시오.

 

마피아가 누구인지 정답을 구하는 것이 아니라 주어진 데이터로 추측할 수 있는 마피아의 최대인원을 구한다는 것에 유의한다.


입력형식

>첫 행에 현재 남은 인원 수 N( 2 ≤ N ≤ 500,000)이 입력된다. 게임에 참여중인 사람의 번호는 1 ~ N이다. 이 후 N개의 행에 걸쳐 Ai가 입력되는데 Ai는 i번째 사람으로부터 마피아라고 지목 받은 사람이 Ai라는 의미이다.

출력형식

마피아로 추측되는 최대 인원은 몇 명인지 출력한다. <입력 예 1에 대한 설명> 마피아는 2와 3이 될 수 있다. <입력 예 2에 대한 설명> 셋 중에 누구든 마피아가 될 수 있지만 가능한 최대 인원은 1명이다. 예를 들어 1번이 마피아라고 할 경우 2번은 평민이다. 3번이 마피아라면 1번을 마피아라고 지목할 수 없으므로 평민이다.

입력 예

3
2
1
1

출력 예

2

입력 예

3
2
3
1

출력 예

1

입력 예

7
3
3
4
5
6
4
4

출력 예

4


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP