(C++) 백준 18310 안테나

문제 및 풀이

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

와압 ㅎ 어려웠다..

먼저 집이 있는 위치들을 vector<int> v 에 입력받고 오름차순으로 sort해서 v[0]부터 마지막 값인 v[v.size()-1] 까지 1씩 증가시키면서 모두 탐색했다.

문제를 풀기 위해 안테나 위치가 1씩 증가할때 마다 안테나 위치보다 작은 위치에 있는 집들은 안테나와의 거리가 1씩 증가하고, 안테나보다 큰 위치에 있는 집들은 안테나와의 거리가 1씩 감소한다는 사실을 이용했다. 이를 사용하면 안테나와 집들 사이의 거리를 계산 한번으로 구할 수 있다.

    for(int i=v[0]; i<=v[v.size()-1]; i++){

        tmp += cnt; // i값보다 작은 위치의 집 갯수만큼 증가
        tmp -= N-cnt; // i값보다 큰 위치의 집 갯수만큼 감소
        // 안테나는 집이 있는 위치에만 설치 가능 : m[i]>0
        // 안테나와 집들간의 거리값이 최소 : MIN>tmp
        // 두가지를 모두 만족하면 답 갱신 
        if(MIN>tmp && m[i]>0) {
            MIN=tmp;
            ans = i;
        }  
        cnt+=m[i];
    }

풀고나서 다른코드들 보니 허무할만큼 간단하게 풀수있는 문제였다 ;;; 정렬하고 가운데 위치하는 값이 무조건 정답이다. 처음에는 직관적으로 안와닿았는데 다음 블로그글 보고 이해했다.

• https://livlikwav.github.io/algorithm/boj-18310/

코드 1

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

int N,x;
long long total;
vector<int> v;
map<int, int> m;

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>N;
    for(int i=0; i<N; i++) {
        cin>>x;
        total+=x;
        if(m[x]==0) v.push_back(x);

        m[x]++;
    }

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

    int ans=1;
    long long cnt=0;
    long long MIN=total;
    long long tmp=total;

    for(int i=v[0]; i<=v[v.size()-1]; i++){

        tmp += cnt;
        tmp -= N-cnt;
        if(MIN>tmp && m[i]>0) {
            MIN=tmp;
            ans = i;
        }  
        cnt+=m[i];
    }


    cout<<ans;
}

코드2

#include <iostream>
#include <algorithm>

using namespace std;
 
int N;
int arr[200005];
int ans;

void solve(){
	sort(arr, arr + N);
	ans = arr[(N - 1) / 2];
}


int main(){

	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	solve();
	cout << ans << '\n';

	return 0;
}