[BOJ] 백준 18310번 - 안테나(with Java)

알고리즘

잘못된 아이디어를 떠올려서 시간초과가 난 이유에 대해서 고민하다가 결국 풀지 못하고 구글링을 통해서 해결하였다.

처음에는 각각의 집에 대해서 다른 집들과의 거리의 합을 비교해서 합이 최소인 집을 구하는 방식으로 접근하였다.

하지만 입력이 최대 20만에 도달했기 때문에 시간복잡도는 O(N^2)로 시간초과가 나게 돼서 풀이에 실패하였다.

 

구글링을 통해서 다른 사람들이 푼 코드를 참고해보니 풀이가 의외로 간단하였다.

집들을 전부 오름차순으로 정렬시킨 후에 중간에 위치한 집을 찾는 것이 전부였다.

알고리즘을 위와 같이 짜게 되면, 어떤 테스트케이스가 주어져도 각각의 집에 대한 합이 최소값을 이루게 된다.

소스코드

문제링크

18310번: 안테나