시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 452 | 173 | 135 | 42.994% |
메모리에 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개의 줄에는 각각의 파일의 정보를 나타내는 자연수가 주어진다. 각 줄의 맨 마지막에는 -1이 주어진다. 두 파일의 길이와 내용이 모두 동일한 경우는 없다고 가정하자. 파일은 231-1 이하의 자연수로 나타낸다.
첫째 줄에 K의 최솟값을 출력한다.
3 1 2 3 -1 1 2 3 4 -1 1 2 4 5 -1
4