#18310 안테나

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

18310번: 안테나

실버 3의 문제이다. 문제를 천천히 읽어보고 손으로 조금 끄적여 봤을때, 중간값이 답이 될것 같다는 생각이 들기는 했는데 예외가 너무 많을 것 같아서 완전 탐색으로 코드를 작성 했다. 결론은 시간초과였다. 다음은 시간초과의 코드이다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> house;
vector<int> cost;

int main()
{
  //freopen("input.txt","r",stdin);
  int n;
  int idx=0;
  int sum=0;
  cin>>n;
  for(int i=0;i<n;i++){
    int num;
    cin>>num;
    house.push_back(num);
  }
  sort(house.begin(),house.end());
  for(int i=0;i<n;i++){
    sum=0;
    for(int j=0;j<n;j++){
      int std=house[i];
      int now=house[j];
      if(std>=now)
        sum+=(std-now);
      else
        sum+=(now-std);
    }
    cost.push_back(sum);
  }

  int idx_cost=*min_element(cost.begin(),cost.end());
  for(int i=0;i<n;i++){
    if(cost[i]==idx_cost){
      idx=i;
      break;
    }
  }
  cout<<house[idx];
}

일단 N의 조건이 20만이다. 그런데 코드에서 N에대한 2중 for문이 나온다. 이것부터가 시간초과의 징조이다. 시간복잡도는 O(N^2) 로, 20만일때는 총 계산 수는 대략 400억으로 문제의 제한인 2초로는 계산 할 수 없다.

 

그래서 처음 생각했던 방법인 중간값이 답이되는지를 생각 해보았다. 중간값을 지정했을때, 양끝으로 갈 수록 거리가 늘어난다. 직관적으로 생각해보아도 왼쪽 끝에서부터 오른쪽 끝까지 거리를 재는 것 보다  중간 어떤 점에서 양끝으로 거리를 재는것이 짧은것을 생각 할 수 있다. 따라서 코드를 다음과 같이 바꾸었다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> house;

int main()
{
  freopen("input.txt","r",stdin);
  int n;
  int ans=0;
  cin>>n;
  for(int i=0;i<n;i++){
    int num;
    cin>>num;
    house.push_back(num);
  }
  sort(house.begin(),house.end());
  ans=house[(n-1)/2];
  cout<<ans;
}

결과는 정답! 사실상 수학 문제였다..!