시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 96 | 42 | 29 | 36.250% |
중부 내륙선은 2021년 12월 31일에 개통된 단선 철도입니다. 하행 열차는 부발역을 출발하여 가남, 감곡장호원, 앙성온천, 충주 순으로 멈추고, 상행 열차는 충주를 출발하여 앙성온천, 감곡장호원, 가남, 부발역 순으로 멈춥니다. 각 구간의 소요 시간은 [표 1]과 같습니다.
구간 | 소요 시간 |
부발 ~ 가남 | 7 |
가남 ~ 감곡장호원 | 7 |
감곡장호원 ~ 앙성온천 | 8 |
앙성온천 ~ 충주 | 10 |
[표 1] 각 구간의 소요 시간
중부내륙선은 단선이어서, 구간에는 한 열차만 운행할 수 있습니다. 하지만, 역에는 상행 열차 여러 대와 하행 열차 여러 대가 동시에 정차할 수 있습니다. 하행 열차와 상행 열차는 아래 알고리즘으로 운행됩니다.
순번 | 하행 | 상행 |
1 | 부발역에서 HH시 mm분에 문을 닫는다. | 충주역에서 HH시 mm분에 문을 닫는다. |
2 | 구간 부발 ~ 가남을 운행한다. | 구간 앙성온천 ~ 충주를 운행한다. |
3 | 1분간 가남역에 머무르고 문을 닫는다. | 1분간 앙성온천역에 머무르고 문을 닫는다. |
4 | 구간 가남 ~ 감곡장호원을 운행한다. | 구간 감곡장호원 ~ 앙성온천을 운행한다. |
5 | 1분간 감곡장호원역에 머무르고 문을 닫는다. | 1분간 감곡장호원역에 머무르고 문을 닫는다. |
6 | 구간 감곡장호원 ~ 앙성온천을 운행한다. | 구간 가남 ~ 감곡장호원을 운행한다. |
7 | 1분간 앙성온천역에 머무르고 문을 닫는다. | 1분간 가남역에 머무르고 문을 닫는다. |
8 | 구간 앙성온천 ~ 충주를 운행한다. | 구간 부발 ~ 가남을 운행한다. |
9 | 충주역에 도착하면 운행을 종료한다. | 부발역에 도착하면 운행을 종료한다. |
[표 2] 하행, 상행 열차의 운행 알고리즘
표 2는 하행 열차와 상행 열차가 시발역에서 종착역까지 가기 위해서 수행하는 일들을 나타냅니다. 이 중 순번 2, 4, 6, 8은 구간을 운행하는 것이므로 관제의 허가를 받아야 합니다. 허가를 받지 못하면 받을 때까지 대기했다가 수행합니다. 하행에서의 A
역 다음 역이 B
역이라고 했을 때, 관제는 구간 A ~ B
에 대해서
A ~ B
를 운행하는 열차가 있는 경우, 다른 열차가 구간 A ~ B
에 접근하는 것을 허용하지 않습니다.A
역에서 구간 A ~ B
를 운행하려고 하는 하행 열차 h
만 있다면, h
가 구간 A ~ B
를 운행하는 것을 허용합니다.B
역에서 구간 A ~ B
를 운행하려고 하는 상행 열차 s
만 있다면, s
가 구간 A ~ B
를 운행하는 것을 허용합니다.A ~ B
를 운행하는 것을 허용합니다.A ~ B
를 운행하는 것을 허용합니다.충주로 향하는 하행 열차 C편성, 부발로 향하는 상행 열차 H편성이 있을 때, 각 편성이 종착역에 도착하는 시각을 구해 주세요.
첫 번째 줄에 C와 H가 공백을 구분으로 해서 주어집니다.
다음 C개의 줄에는 충주로 향하는 하행 열차의 번호와, 해당 열차가 시발역에서 운행을 시작한 시각이 HH:mm
형식으로 주어집니다.
다음 H개의 줄에는 부발로 향하는 상행 열차의 번호와, 해당 열차가 시발역에서 운행을 시작한 시각이 HH:mm
형식으로 주어집니다.
각 열차가 종착 (상행선의 경우 부발, 하행선의 경우 충주)역에 도착하는 시각을 열차 번호 오름차순으로 출력해 주세요. 시각은 HH:mm
형식으로 출력해 주세요.
자정이 넘어 도착하는 경우, 다음날 HH:mm
에 도착했다고 출력해 주세요.
HH:mm
형식입니다. 이때, HH
는 0 이상 23 이하의 정수로, mm
은 0 이상 59 이하의 정수로 주어집니다. HH
와 mm
은 10보다 작으면 앞에 0이 붙습니다.1 1 731 07:10 732 07:20
07:45 07:58
731 열차가 감곡장호원 역을 출발한 07시 26분에, 731과 732의 상황은 [표 3]과 같습니다.
편성 | 수행하고 있는 알고리즘 | 알고리즘을 마치는 시각 |
731 | 감곡장호원역을 출발, 감곡장호원 ~ 앙성온천 구간 운행중 | 07시 34분 |
732 | 충주역을 출발, 앙성온천 ~ 충주 구간 운행중 | 07시 30분 |
[표 3] 731과 732의 07시 26분에 수행하고 있는 알고리즘
732가 감곡장호원 ~ 앙성온천 구간을 운행하기 위해, 관제의 허가를 받습니다. 그런데, 관제는 731이 감곡장호원 ~ 앙성온천을 운행하고 있기 때문에, 관제는 731이 앙성온천역에 도착할 때 까지 732가 감곡장호원 ~ 앙성온천 구간에 접근하는 것을 허용하지 않습니다. 732가 해당 구간에 접근하는 것은 7시 34분이므로, 앙성온천역에 예정보다 3분 더 머무르게 됩니다. 따라서, 732는 종착역에 3분 늦게 도착합니다.
2 1 731 07:10 733 07:18 732 23:50
07:45 00:25 07:55
731은 733의 선행 열차이고, 732는 731보다 16시간 40분 뒤에 출발합니다. 따라서, 731은 부발에서 충주까지 가는 데 35분이 걸립니다. 733은 731의 후행 열차이므로, 733이 구간에 들어가려고 할 때, 731이 해당 구간에 운행을 할 수 있습니다. [표 4]는 731과 733이 언제 운행 알고리즘을 수행하는지 나타냅니다.
순번 | 731 | 733 |
1 | 07:10 | 07:18 |
2 | 07:10 ~ 07:17 | 07:18 ~ 07:25 |
3 | 07:17 ~ 07:18 | 07:25 ~ 07:26 |
4 | 07:18 ~ 07:25 | 07:26 ~ 07:33 |
5 | 07:25 ~ 07:26 | 07:33 ~ 07:34 |
6 | 07:26 ~ 07:34 | 07:34 ~ 07:42 |
7 | 07:34 ~ 07:35 | 07:42 ~ 07:43 |
8 | 07:35 ~ 07:45 | |
9 | 07:45 |
[표 4] 731과 733의 운행 알고리즘을 수행하는 시각
[표 4]에서, 731이 앙성온천 ~ 감곡 구간을 07시 35분부터 07시 45분까지 운행함을 알 수 있습니다. 733은 앙성온천역에 07시 42분에 도착하였고, 1분간 머무른 다음 07시 43분에 순번 8을 수행하려고 합니다. 그런데, 이미 731이 순번 8을 07시 45분까지 수행하고 있으므로, 733은 앙성온천역에 2분 더 머무르게 됩니다. 따라서, 733은 종착역인 충주역에 2분 늦게 도착합니다.
1 1 731 07:32 732 07:20
08:14 07:55
731 열차는 가남역에 07시 39분에, 732 열차는 감곡장호원역에 07시 39분에 도착합니다. 07시 40분에 두 열차는 가남 ~ 감곡장호원 구간을 운행하기 위해 관제에 허가를 받아야 합니다. 관제는 기준 2 - 3 - 1에 따라 시발역에서 먼저 운행을 시작한 732 열차에게 가남 ~ 감곡장호원 구간을 운행하는 것을 허가합니다. 그 이후에 일어나는 일들은 [표 6]과 같습니다.
시간 | 731 | 732 |
07:40 | 가남역에서 대기 | 가남 ~ 감곡장호원 구간 운행 |
07:47 | 732가 가남에 도착했으므로 가남역 출발 |
가남역 도착 |
... | ... | ... |
정시보다 7분 늦게 충주 도착 | 정시에 부발 도착 |
[표 6] 731과 732가 가남 ~ 감곡장호원 구간을 운행하는 시각
1 1 731 07:10 732 23:50
07:45 00:25
Contest > BOJ User Contest > 가희와 함께 하는 코딩 테스트 > 가희와 함께 하는 코딩테스트 4회 D번