백준 18310. 안테나

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

18310번: 안테나

 

이 문제는 처음봤을때 그냥 중간값이 정답 아닌가?

라고 생각했다가 좀 생각해보니 아닌것같고 그럼 문제가 너무 쉬어서 에이 아니겠지 하고 다른 방법으로 풀었는데,

풀고나서 찾아보니까 중간값이 맞았다..

 

어쨌든 내가 푼 풀이는 처음에는 브루트포스를 생각해봤다.

하지만 브루트포스로 풀게되면 O(n^2)가 되는데 n이 최대 20만이므로 불가능하다.

 

그래서 다른 방식으로 생각해봤다.

1. 집들의 위치를 오름차순 정렬한다 
2. 모든 집들 사이의 거리를 구한다.
3. 좌측에서부터 우측으로 이동하면서 현재 집 기준 좌측 집들사이의 거리와, 우측 집들사이의 거리를 따로 구한다.

    

예를들어 입력이 다음과 같다면 

5

5 1 7 9 12

 

좌측 거리, 우측 거리는 다음과 같게된다

left	right
0	4+6+8+11
4	2+4+7
2+6	2+5
2+4+8	3

 

반복문을 돌면서

좌측거리는 (현재 집과 좌측집 사이의 거리) * (i+1) 를 더해주고,

우측거리는 (현재 집과 좌측집 사이의 거리) * (n-i-1)를 빼주면 된다.

 

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

int n;
int house[200010];
int dis[200010];

long long CalculateRight()
{
    long long right = 0;
    long long num = 0;
    for(int i = 0; i < n-1; i++)
    {
        num += dis[i];
        right += num;
    }
    return right;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> house[i];

    sort(house, house+n);


    // 집 사이 거리
    for(int i = 1; i < n; i++)
    {
        dis[i-1] = abs(house[i] - house[i-1]);
    }

    long long left = 0, right = CalculateRight();
    long long ans = left + right;
    int ansHouse = house[0];
    for(int i = 0; i < n-1; i++)
    {
        left += dis[i] * (i+1);
        right -= (dis[i] * (n-i-1));

        long long total = left + right;

        // 설치 가능 위치 여러개일 경우 작은 값 출력해야하므로 <= 는 안됨
        if(total < ans)
        {
            ans = total;
            ansHouse = house[i+1];
        }
    }

    cout << ansHouse;


}