BOJ 15975 : 화살표 그리기

• 문제 링크 : boj.kr/15975
• 난이도 : S3
• 태그 : 정렬

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<pll> arr(n);
    for(auto &e : arr) cin >> e.first >> e.second;
    arr.push_back({0, -1});
    arr.push_back({0, 100001});
    sort(all(arr), [](pii a, pii b){
        if(a.second == b.second) return a.first < b.first;
        return a.second < b.second;
    });

    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        ll d = INF;
        if(arr[i].second == arr[i-1].second) d = min(d, abs(arr[i].first - arr[i-1].first));
        if(arr[i].second == arr[i+1].second) d = min(d, abs(arr[i].first - arr[i+1].first));
        if(d != INF) ans += d;
    }
    cout << ans;

    return 0;
}

---

풀이

y로 먼저, 그 다음 x로 정렬하여 같은 색끼리 좌표가 오름차순이 되도록 정렬해준다.

어떤 점의 양 쪽에 있는 점이 가장 가까운 점이 될 후보이다.

둘 중 같은 색이고 거리가 짧은 점을 골라 화살표의 길이를 답에 더해준다.

둘 다 다른 색이라면 같은 색의 점이 없으므로 길이는 0이다.