[BOJ] 24336 가희와 무궁화호

https://www.acmicpc.net/problem/24336

24336번: 가희와 무궁화호

문제

아래 [표 1]은 경부선에서 무궁화호가 정차하는 역을 나타냅니다.

역 번호	역 이름	거리(km)	필수 정차 여부	역 번호	역 이름	거리(km)	필수 정차 여부
1	Seoul	0.0	Y	23	Chupungnyeong	234.7	N
2	Yeongdeungpo	9.1	Y	24	Gimcheon	253.8	Y
3	Anyang	23.9	N	25	Gumi	276.7	Y
4	Suwon	41.5	Y	26	Sagok	281.3	N
5	Osan	56.5	N	27	Yangmok	289.5	N
6	Seojeongri	66.5	N	28	Waegwan	296.0	Y
7	Pyeongtaek	75.0	Y	29	Sindong	305.9	N
8	Seonghwan	84.4	N	30	Daegu	323.1	Y
9	Cheonan	96.6	Y	31	Dongdaegu	326.3	Y
10	Sojeongni	107.4	N	32	Gyeongsan	338.6	N
11	Jeonui	114.9	N	33	Namseonghyeon	353.1	N
12	Jochiwon	129.3	Y	34	Cheongdo	361.8	N
13	Bugang	139.8	N	35	Sangdong	372.2	N
14	Sintanjin	151.9	N	36	Miryang	381.6	Y
15	Daejeon	166.3	Y	37	Samnangjin	394.1	N
16	Okcheon	182.5	N	38	Wondong	403.2	N
17	Iwon	190.8	N	39	Mulgeum	412.4	N
18	Jitan	196.4	N	40	Hwamyeong	421.8	N
19	Simcheon	200.8	N	41	Gupo	425.2	Y
20	Gakgye	204.6	N	42	Sasang	430.3	N
21	Yeongdong	211.6	Y	43	Busan	441.7	Y
22	Hwanggan	226.2	N

[표 1] 경부선에서 무궁화호가 정차하는 역들

[표 1]에서 역 이름과 각각의 역에 대응되는 역 번호가 있습니다. Seoul 역은 1번, Busan역은 43번입니다. 역 번호가 증가하는 방향은 하행이고, 역 번호가 감소하는 방향은 상행입니다. 예를 들어 1번 Seoul 역에서 31번 Dongdaegu 역으로 가는 경우, 역 번호가 증가하는 방향이므로 하행이고, 43번 Busan 역에서 15번 Daejeon 역으로 가는 방향은 역 번호가 감소하는 방향이므로 상행입니다.

[표 1]에서 거리란 Seoul 역으로부터의 거리를 의미합니다. 예를 들어 22번 Hwanggan 역은 1번 Seoul 역으로부터 226.2km 떨어져 있습니다.

가희가 타고 있는 무궁화호가 k개의 역, S1, S2, ... , Sk 순서대로 정차한다고 해 보겠습니다. 즉, x번째로 정차하는 역은 Sx입니다. 이때, 무궁화호는 S1 역을 출발, S2 역 도착, S2 역 출발, ... , Sk 역 도착순으로 수행하게 됩니다.

무궁화호가 시각 hh:mm에 역에 도착하거나 출발하는 것을 이벤트라고 정의하겠습니다. 가희가 타고 있는 무궁화호의 x번째 이벤트는 아래와 같이 정의됩니다.

• x가 홀수일 때, 무궁화호가 S⌊x/2⌋+1 번째 역을 출발
• x가 짝수일 때, 무궁화호가 S⌊x/2⌋+1 번째 역에 도착
• ⌊x⌋는 내림을 의미합니다.

예를 들어, 가희가 탄 무궁화호가 아래 [표 2]와 같이 18개 역을 순서대로 정차한다고 하겠습니다.

순번	역 이름	순번	역 이름
1	Seoul	10	Gumi
2	Yeongdeungpo	11	Waegwan
3	Suwon	12	Daegu
4	Pyeongtaek	13	Dongdaegu
5	Cheonan	14	Gyeongsan
6	Jochiwon	15	Cheongdo
7	Daejeon	16	Miryang
8	Yeongdong	17	Gupo
9	Gimcheon	18	Busan

[표 2] 가희가 탄 무궁화호가 Seoul 역에서 Busan 역까지 가는 동안 정차하는 역의 예

가희가 탄 무궁화호는 18개 역에 정차하고, 이 중 3번째로 정차하는 역은 Suwon 역입니다. 또한, 3번째로 발생하는 이벤트는 Yeongdeungpo 역을 출발하는 것입니다.

가희가 타고 있는 무궁화호의 x번째 이벤트가 hhx:mmx에 발생했고, x+1번째 이벤트가 hhx+1:mmx+1에 발생했다고 해 보겠습니다.

• 시각 hhx:mmx이 시각 hhx+1:mmx+1보다 앞선다면, x번째 이벤트와 x+1번째 이벤트는 같은 날에 발생합니다.
• 그렇지 않으면 x번째 이벤트가 발생한 날 다음날에 x+1번째 이벤트가 발생합니다.

가희는 가희가 타고 있는 열차의 시간표를 보고, 특정 구간의 표정속도를 구하고 싶습니다. 가희를 도와주세요.

표정속도란, 일정 거리를 주행했을 경우 그 거리를 소요된 총 시간(주행 시간 + 정차 시간)으로 나누어 구한 속도를 의미합니다.

입력

첫 번째 줄에 가희가 타고 있는 열차의 정차역 개수 N과 가희의 질문 개수 Q가 주어집니다.

두 번째 줄부터 N개의 줄에 걸쳐서 정차역 이름과 도착 정보, 출발 정보가 공백을 구분으로 해서 주어집니다. 열차가 정차하는 순서대로 주어지며, 첫 번째로 주어지는 역은 시발역, 마지막으로 주어지는 역은 종착역입니다.

도착 정보와 출발 정보는 아래와 같이 주어집니다.

• 시발역 (열차가 운행을 시작하는 역)에 대한 도착 정보는 -:-로 주어집니다.
• 종착역 (열차가 운행을 종료하는 역)에 대한 출발 정보는 -:-로 주어집니다.
• 그 외에는 출발 정보와 도착 정보는 hh:mm 형식으로 주어집니다. hh:mm 형식은
  • hh는 0 이상 23 이하의 정수, mm은 0 이상 59 이하의 정수로 주어집니다. 만약, 한 자리 숫자면 앞에 0을 붙입니다.

N+2번째 줄부터 Q개의 줄에 걸쳐서 station1과 station2가 공백을 구분으로 해서 주어집니다.

이는 가희가 타고 간 열차의 운행 구간 station1 ~ station2의 표정속도(km/h)를 구하라는 의미입니다.

출력

Q개의 질문에 대한 답을 한 줄에 하나씩 출력해 주세요. 모범 답안과의 절대/상대 오차가 10-6 이하인 경우 정답으로 인정됩니다.

제한

• 2 ≤ N ≤ 43
• 1 ≤ Q ≤ N×(N−1)2$\dfrac{N×(N-1)}{2}$ 
• 열차는 정차하는 모든 역에 대해 정시에 출발하고 정시에 도착합니다.
• 주어진 N개의 역은 모두 경부선에 있습니다.
• 열차가 시발역에서 종착역에 갈 때까지 소요 시간은 1시간 이상 6시간 이하입니다.
• 시발역과 종착역은 Seoul, Daejeon, Dongdaegu, Busan 중 하나이며, 시발역과 종착역이 같은 경우는 주어지지 않습니다.
• 열차의 시발역이 A이고 종착역이 B라고 했을 때
  • 열차가 중간에 방향을 바꾸는 일이 없습니다.
  • A에서 B로 갈 때 반드시 정차해야 하는 필수 정차역 (필수 정차 여부가 Y라고 표시된 역)이 누락되는 경우는 없습니다.
• 특정 구간의 표정속도를 구해야 하는 질문 station1 station2가 주어질 때
  • 가희가 타고 있는 열차가 정차하지 않는 역은 주어지지 않습니다.
  • 가희가 타고 있는 열차의 방향과 station1에서 station2로 향하는 방향은 같습니다.
  • 같은 역 2개가 주어지지 않습니다.
• 가희가 타고 있는 열차는 경부선 외에 다른 노선을 경유하지 않습니다.

풀이

한 눈에 보면 굉장히 어렵고 복잡해 보이지만, 실제로는 정말 정말 간단한 구현 문제였다..... 설명이 복잡하지만 결국에는 구해야할 두 역 사이의 거리를 시간차로 나누기만 하면 되는 문제였다. 번지르르한 설명은 그냥 무시해도 되는 부분이었다. 이번에 열린 가희와 함께하는 3회 코딩테스트를 참가하며 처음으로 참가하는 대회?여서 긴장했던 것 같다. 시간이 많이 걸리는 부분은 역에 대한 정보를 입력하는 부분이라고 할 수 있다. 나 같은 경우에는 역의 이름을 키값 거리를 value값으로 줘서 딕셔너리 형태로 저장했다. 두 역을 입력 받고 시간 차를 구한 다음 거리의 절대값을 시간 차로 나눠주었다.

import sys
input = lambda: sys.stdin.readline().rstrip()
n, q = map(int, input().split())
train = {
  "Seoul": 0.0,
    "Yeongdeungpo": 9.1,
    "Anyang": 23.9,
    "Suwon": 41.5,
    "Osan": 56.5,
    "Seojeongri": 66.5,
    "Pyeongtaek": 75.0,
    "Seonghwan": 84.4,
    "Cheonan": 96.6,
    "Sojeongni": 107.4,
    "Jeonui": 114.9,
    "Jochiwon": 129.3,
    "Bugang": 139.8,
    "Sintanjin": 151.9,
    "Daejeon": 166.3,
    "Okcheon": 182.5,
    "Iwon": 190.8,
    "Jitan": 196.4,
    "Simcheon": 200.8,
    "Gakgye": 204.6,
    "Yeongdong": 211.6,
    "Hwanggan": 226.2,
    "Chupungnyeong": 234.7,
    "Gimcheon": 253.8,
    "Gumi": 276.7,
    "Sagok": 281.3,
    "Yangmok": 289.5,
    "Waegwan": 296.0,
    "Sindong": 305.9,
    "Daegu": 323.1,
    "Dongdaegu": 326.3,
    "Gyeongsan": 338.6,
    "Namseonghyeon": 353.1,
    "Cheongdo": 361.8,
    "Sangdong": 372.2,
    "Miryang": 381.6,
    "Samnangjin": 394.1,
    "Wondong": 403.2,
    "Mulgeum": 412.4,
    "Hwamyeong": 421.8,
    "Gupo": 425.2,
    "Sasang": 430.3,
    "Busan": 441.7,
}
destination = {}
for i in range(n):
  name, st, et = input().split()
  destination[name] = []
  if st[0] == '-':
    destination[name].append([])
    destination[name].append(list(map(int, et.split(':'))))
  elif et[0] == '-':
    destination[name].append(list(map(int, st.split(':'))))
    destination[name].append([])
  else:
    destination[name].append(list(map(int, st.split(':'))))
    destination[name].append(list(map(int, et.split(':'))))
for _ in range(q):
  s1, s2 = input().split()
  distance = abs(train[s2]-train[s1])
  t = 0
  if destination[s2][0][1] < destination[s1][1][1]:
    t -= 1
    t += (destination[s2][0][1] +60 - destination[s1][1][1])/60 
  else:
    t += (destination[s2][0][1] - destination[s1][1][1]) /60
  if destination[s2][0][0] < destination[s1][1][0]:
    t += (destination[s2][0][0] + 24 - destination[s1][1][0])
  else:
    t += (destination[s2][0][0] - destination[s1][1][0])
  print(distance / t)

어려워보이는 속임수에 속지말자...ㅠ