문제 링크: https://www.acmicpc.net/problem/30405

아이디어만 떠올리면 구현은 쉬운 문제입니다.

풀이

모든 고양이의 이동 거리의 합을 최소로?

문제 입력에서 각각의 고양이가 박물관을 견학하는 순서를 주지만, 사실 고려할 필요가 없습니다.

어느 박물관을 출입점으로 정하던 각각의 고양이가 자신이 정한 순서로 박물관을 견학하는 총 거리는 항상 일정합니다. (출입문 -> 견학 시작 지점, 견학 종료 지점 -> 출입문의 거리는 제외)

즉, 출입문부터 견학이 시작되는 지점까지의 거리와 견학이 종료되는 지점 -> 출입문 까지의 거리만 변하기 때문에, 이 거리의 합이 최소가 되는 지점을 찾으면 됩니다.

그런데, 거리의 합이 최소가 되는 경우는 가장 많은 고양이가 견학의 시작 지점 또는 종료 지점으로 삼은 박물관에 출입문을 배치하는 경우일 것입니다.
따라서, 이 문제는 거리의 합을 계산하는 대신 고양이의 견학 시작 지점과 종료 지점들을 모아둔 배열에서 가장 많이 등장하는 박물관 번호를 찾는 문제로도 해석할 수 있습니다.

가장 많이 등장하는 수 찾기

최빈값을 찾는 문제이지만, 최빈값을 찾기 위해서는 배열 전체를 순회하며 개수를 파악해야 합니다.

하지만, 배열을 정렬해버리면 가장 많이 등장한 값이 중앙에 위치할 것입니다. 즉, 정렬된 배열의 중앙값이 답이 됩니다.

이때, "둘 이상의 박물관을 출입점으로 잡아도 거리 합이 같다면 그 중 가장 작은 번호를 출력하라" 는 조건이 있습니다.

지금 정렬한 배열은 각 고양이의 견학 시작 지점과 종료 지점을 저장한 배열이므로, 고양이의 수의 2배인 $2N$의 길이를 가지며 항상 짝수입니다.
길이가 짝수인 경우 중앙값은 $N-1$ 또는 $N$이 해당하는데, 위 조건에 따라 번호가 작은 쪽인 $N-1$에 위치한 값이 답이 됩니다.

전체 코드

input = open(0).readline

N, M = map(int, input().split())

entrances = []

for i in range(N):
    k, start, *_, end = map(int, input().split())
    entrances.append(start)
    entrances.append(end)

entrances.sort()

print(entrances[N - 1])