Joonas' Note

Joonas' Note

BOJ 3075 - Astromeeting 본문

알고리즘/문제 풀이

BOJ 3075 - Astromeeting

2018. 4. 18. 22:28 joonas

    링크: 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 15656 - 치킨 배달  (0) 2018.04.17
    BOJ 15685 - 드래곤 커브  (0) 2018.04.17
    BOJ 12755 - 수면 장애  (0) 2018.04.17
    Comments