IOI 1994 day2 2- 버스 정거장(The Buses) > 문제은행 : 정보올림피아드&알고리즘




1193 : 버스 정거장(The Buses)

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
14 회   
시도횟수
96 회   

문제

어떤 사람이 버스 정거장에 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개 노선이 최소 노선 수임을 알 수 있다.

 


입력형식

입력 파일의 첫 줄에는 모든 노선들의 도착횟수 (n≤300)이 적혀 있고 그 다음 줄에는 모든 노선의 도착 시간들이 오름차순으로 적혀 있다. 도착 시간은 0에서 59 사이의 분 단위로 표시되며 답이 되는 노선의 수는 17보다 작거나 같다.

출력형식

위의 버스 도착 시간을 모두 포함하는 최소의 노선 수를 출력하시오. 버스의 도착 시간은 다른 노선의 버스가 같은 시각에 처음 도착할 수도 있고 또 배차 간격이 같을 수도 있다. 처음 도착 시간과 배차 간격이 모두 같은 노선들이 있을 경우에 이 노선들은 서로 다른 것으로 취급되어야 한다.

입력 예

17
0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53

출력 예

3


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP