새내기와 헌내기
면접 대비시간 제한2초메모리 제한256 MB
신입은 진실만, 베테랑은 거짓만 말한다는 규칙 아래 참가자 N명의 신고 관계가 주어질 때 가능한 베테랑 수의 최댓값을 구한다.
문제
종우는 SPC(Saenaegi Programming Contest)의 주최자이다. SPC는 그 이름처럼 새내기만을 대상으로 하는 대회이다. 그런데 종우는 SPC의 참가자에 몰래 헌내기가 섞인 것이 아닌지 의심이 들었다. 그래서 종우는 참가자 각자에게 알고 있는 헌내기를 지목해달라고 하여 헌내기 신고를 받기로 했다.
그런데 모든 신고를 곧이곧대로 믿을 수는 없다. 헌내기 신고를 한 당사자가 새내기인지 헌내기인지 아직 모르기 때문이다. 새내기가 한 신고라면 괜찮겠지만, 헌내기가 자신은 새내기인 척 다른 사람을 신고할 수도 있다. 이 경우에는 신고를 믿기 어려워진다. 종우는 이를 곰곰이 생각하다가 아래와 같은 규칙이 있다는 것을 깨달았다.
- 모든 참가자는 각각 새내기 또는 헌내기 둘 중 하나이다.
- 만약 어떤 참가자가 새내기라면, 그 사람이 제보한 신고는 모두 사실이다.
- 만약 어떤 참가자가 헌내기라면, 그 사람이 제보한 신고는 모두 거짓이다.
신고가 사실이라는 것은 신고를 당한 대상이 헌내기가 맞다는 것이고, 반대로 거짓이라는 것은 신고를 당한 대상이 새내기라는 것이다. 이제 종우는 최악의 상황, 다시 말해 헌내기가 제일 많을 때를 대비하려 한다. 그렇다면 현재 신고 상황에서 가능한 경우들 내에서 헌내기는 최대 몇 명 존재할 수 있을까? 이를 계산해보자.
입력
첫째 줄에 참가자 수를 의미하는 정수 N(1 ≤ N ≤ 2,000)이 주어진다.
다음 N개의 줄에는 N개의 문자로 현재 신고 상황이 주어진다. x번째 줄의 y번째 문자가 1이면 x번 참가자가 y번 참가자를 신고한 것이고, 0이면 신고하지 않은 것이다.
주어지는 입력이 본문에 제시된 규칙과 모순된 경우는 없다.
출력
본문의 규칙을 따를 때 현재 신고 상황에서 가능한 최대 헌내기 인원수를 출력한다.