BOJ 3075 - Astromeeting

링크: https://www.acmicpc.net/problem/3075

문제

p개의 은하가 있을 때, n명과 교통비의 합이 최소가 되는 어떤 하나의 은하(미팅 장소)를 찾는 문제이다.

조심할 것

조건이 특별히 안 적혀있어서 조심해야 할 게 많은 문제였다. 주의해야 할 조건으로는

1. 하나의 은하에 여러 사람이 있을 수 있고

2. 은하와 은하 사이에는 여러 개의 길이 존재할 수 있다

(doju님의 데이터 추가 글)

나는 외딴 섬에 대한 케이스를 처리 못해서 틀렸었다.

풀이

미팅 장소가 될 은하를 하나 잡고, 그 은하로부터 나머지 사람들과의 거리의 합을 구한다. 이 때, 거리의 합이 최소가 되는 은하가 정답이다.

은하의 개수 \(p \lt 100\) 로 작은 크기이기 때문에, 플로이드-와샬 알고리즘으로 구현하면 간단하다. \(O(n^3)\)

코드