시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 45 19 9 47.368%

문제

메모리에 N개의 파일이 저장되어 있다. 이 문제에서는 편의상 각각의 파일을 수열과 같이 생각하자. 이와 같은 파일들을 구별하기 위해서는 두 개의 파일을 맨 끝까지 읽어보는 작업을 수행해야 한다. 이와 같은 작업을 좀 더 효율적으로 수행하기 위해서, 파일의 앞에서부터 차례로 K번째 수 까지만 읽어보는 방법이 있다. 만약 파일의 크기가 K보다 작다면 파일의 뒤에 0이 여러 개 붙어서 총 길이를 K로 만드는 것으로 생각하면 된다.

예를 들어 {1, 2, 3}, {1, 2, 3, 4}, {1, 2, 4, 5}과 같은 세 개의 파일이 있다고 해 보자. K=3일 경우 각 파일의 앞에서부터 K번째 수 까지 읽으면 {1, 2, 3}, {1, 2, 3}, {1, 2, 4}이 된다. 이 경우에는 서로 같은 경우가 있으므로 파일들을 완전히 구별할 수 없다. 하지만 K=4일 경우 {1, 2, 3, 0}, {1, 2, 3, 4}, {1, 2, 4, 5}가 되어 모든 파일들을 완전히 구별할 수 있게 된다.

N개의 파일에 대한 정보가 주어졌을 때, 모든 파일들을 구별할 수 있게 해 주는 최소의 K값을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 N(1≤N≤100)이 주어진다. 다음 N개의 줄에는 각각의 파일의 정보를 나타내는 자연수(int 범위)가 주어진다. 각 줄의 맨 마지막에는 -1이 주어진다. 두 파일의 길이와 내용이 모두 동일한 경우는 없다고 가정하자.

출력

첫째 줄에 K의 최소값을 출력한다.

예제 입력

3
1 2 3 -1
1 2 3 4 -1
1 2 4 5 -1

예제 출력

4

힌트

출처

  • 잘못된 데이터를 찾은 사람: abckhw