[백준 python] 18310번 안테나 - 그리디

[백준 python] 18310번 안테나 - 그리디

레벨: 실버 3

언어: python

---

📑풀이 과정

1. 모든 경우 계산

처음 문제를 보고 모든 값 집의 위치 마다 거리를 계산 했다.
이 경우 n^2의 시간 복잡도를 가지는데 입력값의 최대가 200,000이라서 무조건 시간 초과가 나오게 된다.

2. 다른 풀이

수학적으로 생각하면 간단하게 풀 수 있는 문제이다.

모든 집까지의 거리의 총합이 가장 작으려면 일직선 상에서 가운데에 가까울 수록 총합이 적어진다.

 

그래서 배열에 집의 위치를 저장하고 정렬 후 중앙값을 찾아서 출력하면 된다.

📋풀이 코드

import sys

input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split(' ')))

arr.sort()
print(arr[(N-1)//2]

---