안테나

• 링크 : https://www.acmicpc.net/problem/18310
  
  

메모

집은 여러 개
그중 안테나는 하나 (집이 있는 곳에만 설치 가능)
같은 위치에 집 여러 개 존재 가능!!

안테나 하나 설치하기로 함

• 그로부터 모든 집까지의 거리 총합이 min이 되는 안테나 설치할 집 위치를 찾아야함
  • 가능하면 집들의 중간점에 설치하는게 이득아닌가?

알고리즘 및 방법

범위가 200,000 인걸 보면, O(nlogn)까지 가능한거같은데

브루트포스로 하게되면..?

틀린사람 비율을 보니 딱봐도 브루트포스로 하다가 다틀렸을수도..?

브루트포스 할 필요도 없네

n = 4
arr.sort()하고
pivot = n // 2    # 중간 집의 위치(=인덱스)

메모에 쓴 것처럼 중간위치가 결국 정답임

• 정확한 중간위치 얻기 위해 정렬을 사용한거

---

추가 테스트케이스

pgen_00.in
3
1 10 10
pgen_00.out
10

pgen_01.in
3
1 1 10
pgen_01.out
1

pgen_02.in
5
1 7 8 9 10
pgen_02.out
8

pgen_03.in
1
90
pgen_03.out
90

---

솔루션 코드 - 내가 푼

• 기본적인 정렬유형 문제

n = int(input())
arr = list(map(int, input().split()))

arr = sorted(arr)
if n <= 2:
    print(arr[0])
else:
    if n % 2 == 0:  # 짝수        
        print(arr[(n//2)-1])
    else:
        print(arr[n//2])

솔루션 코드 - 동빈나

• python

n = int(input())
a = list(map(int, input().split()))
a.sort()

# 중간값(median)을 출력
print(a[(n - 1) // 2])

• cpp

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> v;

int main(void) {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        v.push_back(x);
    }

    sort(v.begin(), v.end());

    // 중간값(median)을 출력
    cout << v[(n - 1) / 2] << '\n';
}