어떤 사람이 버스 정거장에 12시에 도착하였다. 그 사람은 12시부터 12시 59분까지 그곳에 있었다.

그런데, 그 버스 정거장에는 여러 노선의 버스가 정거한다. 그 사람은 버스들이 도착하는 시간들을 적어보았다.

버스들이 도착하는 시간들이 모두 주어졌다.

버스의 도착시간을 정리해본 결과 아래와 같은 규칙성을 찾을 수 있었다.

1. 같은 노선의 버스는 12시에서 12시 59분 사이에 같은 시간 간격으로 다닌다. 2. 각 노선들은 이 시간 사이에 최소 두 번은 도착한다. 3. 서로 다른 노선의 버스가 같은 시각에 도착할 수 있다.

위의 규칙성에 맞추어서 버스의 도착 시간이 분단위로 차례로 열거되어 입력으로 들어올 때,

도착 시간을 모두 포함하기 위한 버스 노선 최소 개수를 알려 한다. 이 때 정류장에 도착하는 배차 간격이 노선마다 다르기 때문에, 버스 노선이 여러 개가 존재한다.

당신은 버스 도착 시간을 모두 포함하는 버스 노선의 수가 최소가 될 때의 노선 수를 알아내는 프로그램을 작성해야 한다.

예를 들어 0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53의 순서로 버스들이 도착했다면,

0분부터 시작하는 배차간격이 13분인 버스 노선과, 3분부터 시작하는 배차 간격 12분인 버스 노선,

그리고 5분부터 시작하는 배차 간격 8분인 버스 노선의 총 3개 노선이 최소 노선 수임을 알 수 있다.

버스 정거장(The Buses) timer 1s memory 64MB

버스 정거장(The Buses) 1s 64MB