궤도

문제 풀이 입력이 100,000개까지 들어올 수 있어서 행성 하나하나마다 모두 거리를 구하면 메모리 초과가 발생한다. 그렇다면 MST에 들어올 가능성이 있는 거리만 저장해야 하는데 그걸 도대체 어떻게 알까? 이 부분 때문에 힘들었다. 두 행성을 연결하는 비용을 살펴보자. 보통의 좌표간 거리 구하기 공식이 아니라 x, y, z 좌표의 차이의 절댓값 중 가장 작은 값을 터널 비용으로 한다고 적혀있다. 그럼 문제를 단순화 해서 x좌표만 존재한다고 하자. 그럼 당연히 예제 입력 1에 대한 MST는 (-1) - (10) - (11) - (14) - (19)로 20일 것이다. 그니까 만약에 최종적으로 x좌표의 차이의 절댓값을 MST의 간선으로 사용하게 된다면...그것은 (-1) - (10), (10) - (11),..