[BOJ] 15970 화살표 그리기 - C++

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

15970번: 화살표 그리기

아이디어

같은 색의 점 중 가장 가까운 점을 찾아서 이으면 된다. 당연히 완전탐색으로는 시간을 맞출 수 없고 정렬을 이용하면 된다. (색, 위치) 순서로 저장해 정렬하면 같은 색끼리 원점에서 멀어지는 순서대로 모이게 된다. $n$번째 점에서 가장 가까운 점은 $n-1$번째나 $n+1$번째 점일 것이다.

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    pair<int, int> a[n];
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a[i] = {y, x};
    }
    sort(a, a + n);

    int ans = 0;
    for (int i = 0; i < n; i++) {
        int d1 = 1e9;
        int d2 = 1e9;

        if (i > 0 && a[i].first == a[i - 1].first) {
            d1 = a[i].second - a[i - 1].second;
        }
        if (i < n - 1 && a[i].first == a[i + 1].first) {
            d2 = a[i + 1].second - a[i].second;
        }

        ans += min(d1, d2);
    }

    cout << ans;
}