점진적 입회
시간 제한2초메모리 제한512 MB
n명의 선수 간 경기 결과가 주어질 때, 탈락 순서를 정해 어떤 시점에서도 아직 입성하지 못한 선수가 이미 입성한 선수를 이긴 경기 수가 k를 넘지 않도록 하는 최소 k를 구한다.
문제
북유럽 대학 핑퐁 선수권 대회(NCPC)는 모든 참가자가 다른 모든 참가자와 정확히 한 경기씩 핑퐁을 치르는 무시무시하게 치열한 토너먼트이다. 대회의 마지막 경기가 방금 끝났으므로, 이제 프로그램에 남은 것은 하나뿐이다. 바로 올해의 모든 참가자가 NCPC 명예의 전당에 입회하는 전통적인 상장 수여식이다.
오래된 관례에 따르면, 아직 명예의 전당에 입회하지 못한 참가자(한심한 무명 선수)는 무대 왼쪽에 있어야 하고, 입회한 참가자(멋진 전설)는 무대 오른쪽에 있어야 한다. 그리고 참가자가 상장을 받을 때, 상징적으로 무대 왼쪽에서 오른쪽으로 걸어가면서 멋진 전설이 된다. 한 번에 한 참가자만 명예의 전당에 입회하며, 모든 참가자는 처음에 왼쪽에서 시작한다.
NCPC 심사위원장은 오른쪽에 있는 멋진 전설이 왼쪽에 있는 한심한 무명 선수에게 진 경기가 너무 많으면 자신의 평판에 나쁘다고 생각하지만, 상장 수여식이 진행되는 동안 매 순간 이를 피하는 것이 불가능할 수도 있다는 것을 금방 깨닫는다. 그러나 그녀는 이런 수치스러운 일을 최소한으로 줄이고 싶어 한다. 구체적으로, 그녀는 다음 조건을 만족하는 상장 수여 순서가 존재하는 가장 작은 수 k를 찾고자 한다. 어떤 순간에도 멋진 전설이 한심한 무명 선수에게 진 경기가 k번을 넘지 않아야 한다.
입력
입력의 첫 줄에는 참가자의 수를 나타내는 정수 n (1 ≤ n ≤ 5 000)이 주어진다. 이어서 n−1개의 줄이 주어지고, i번째 줄에는 길이 i의 이진 문자열이 있다. i번째 줄의 j번째 문자가 1이면 참가자 i + 1이 참가자 j를 이겼다는 뜻이고, 0이면 참가자 j가 참가자 i + 1을 이겼다는 뜻이다.
출력
위의 조건을 만족하는 가장 작은 정수 k를 출력한다.