BOJ 3075 - Astromeeting

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

문제

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

조심할 것

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

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

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

(doju님의 데이터 추가 글)

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

풀이

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

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

코드

반응형

• 카카오스토리
• 트위터
• 페이스북

'알고리즘 > 문제 풀이' 카테고리의 다른 글

BOJ 1525 - 퍼즐  (0)	2018.05.08
BOJ 2225 - 합분해  (0)	2018.04.24
BOJ 3075 - Astromeeting  (0)	2018.04.18
BOJ 15656 - 치킨 배달  (0)	2018.04.17
BOJ 15685 - 드래곤 커브  (0)	2018.04.17
BOJ 12755 - 수면 장애  (0)	2018.04.17