- Today
- 27
- Total
- 237,967
Notice
Recent Posts
Recent Comments
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |
Archives
- 2022/06 (8)
- 2022/05 (5)
- 2022/04 (11)
- 2022/03 (11)
- 2022/02 (1)
- 2022/01 (2)
- 2021/11 (2)
- 2021/10 (2)
- 2021/09 (4)
- 2021/02 (1)
- 2020/07 (1)
- 2020/06 (6)
- 2020/05 (5)
- 2020/04 (5)
- 2020/03 (5)
- 2020/02 (6)
- 2020/01 (6)
- 2019/12 (7)
- 2019/11 (8)
- 2019/09 (7)
- 2019/06 (2)
- 2019/05 (6)
- 2019/04 (4)
- 2019/03 (8)
- 2019/02 (5)
- 2019/01 (2)
- 2018/11 (7)
- 2018/10 (10)
- 2018/09 (2)
- 2018/07 (2)
Joonas' Note
BOJ 3075 - Astromeeting 본문
링크: https://www.acmicpc.net/problem/3075
문제
p개의 은하가 있을 때, n명과 교통비의 합이 최소가 되는 어떤 하나의 은하(미팅 장소)를 찾는 문제이다.
조심할 것
조건이 특별히 안 적혀있어서 조심해야 할 게 많은 문제였다. 주의해야 할 조건으로는
1. 하나의 은하에 여러 사람이 있을 수 있고
2. 은하와 은하 사이에는 여러 개의 길이 존재할 수 있다
나는 외딴 섬에 대한 케이스를 처리 못해서 틀렸었다.
풀이
미팅 장소가 될 은하를 하나 잡고, 그 은하로부터 나머지 사람들과의 거리의 합을 구한다. 이 때, 거리의 합이 최소가 되는 은하가 정답이다.
은하의 개수 \(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 |
0 Comments