[BOJ 18310, Python 3] 안테나

알고리즘/BOJ 2021. 8. 3. 15:59

18310번: 안테나

첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다.

www.acmicpc.net

y = | x - x1 | + | x - x2 | + | x - x3 | + .... + | x - xn | 로 그래프를 그려보면 대충 아래와 같은 모양이 나옵니다.

같은 거리의 집도 있으니 좀 찌그러진 2차함수 모양이겠네요.

여기서 n이 홀수이면 최소값이 딱 하나 나옵니다.

n이 짝수이면 최소값이 두 개 나옵니다.

그림은 y축이 살짝 다르지만 (n - 1)/2 값과 n / 2 값이 같다고 생각해주세요.

그래서 n이 홀수이면 n/2번째 집, n이 짝수이면 번호가 작은 것을 출력해야하므로 (n-1)/2로 출력해주면 됩니다.

이 방식을 사용하는 문제는 가끔가다 보여서 기억해두면 좋을 것 같습니다.

1
2
3
4

n = int(input())
arr = sorted([*map(int,input().split())])
if n % 2: print(arr[n//2])
else:print(arr[(n-1)//2])

cs

70825 70825