[BOJ] 18310번_안테나_정렬 (C++)

[문제]

https://www.acmicpc.net/problem/18310

일직선 상의 마을에 여러 채의 집이 존재하는데 이중에서 모든 집에 닿도록 한 집에 안테나를 설치하는 문제이다. 한 집에서 다른 모든 집까지의 거리의 총합이 가장 작은 집을 구하면되는 문제이다.

• 처음엔 한 집에서 다른 모든 집까지의 거리의 합을 모두 구해서 최소값을 구하려고 했으나, 문제를 자세히 보니 그냥 입력받은 수들의 중간값을 구하면되는 간단한 문제였다.
  당연한 소리지만 끝에서 끝까지 전파가 닿도록 설치하는 것보다 중앙에서 양쪽 끝에 전파가 닿는 것이 효율이 좋기때문이다.

[사용 알고리즘]

정렬

[풀이 핵심]

• 입력받은 수를 vector에 저장해 준 다음 algorithm헤더의 sort함수를 사용해 정렬한다.
• 정렬한 vector의 중간 값이 정답이다. (안테나를 설치할 수 있는 위치 값으로 여러 개의 값이 도출될 경우 가장 작은 값을 출력하라는 조건이 있으므로 int형으로 나누기 연산을 진행하여 소수점 아래 데이터를 버려주었다.)

[코드]

//boj18310번_안테나_그리디 알고리즘

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	int N;
	cin >> N;

	vector<int> v;

	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		v.push_back(num);
	}

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

	cout << v[(v.size() - 1) / 2];

	return 0;
}