[ 백준 ] 15975 / 화살표 그리기

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
67/228
post-thumbnail

# Appreciation

/*
 * Problem :: 15975 / 화살표 그리기
 *
 * Kind :: Sorting
 *
 * Insight
 * - 같은 색상인것들끼리 정렬하면 될것 같은데...?
 *   + (좌표, 색깔) = (x, y) 를
 *     실제 2D 좌표로 생각해버리고
 *     y 좌표가 같은 점들끼리의
 *     가장 가까운 좌표까찌 거리의 합
 *     이라고 생각하면 될듯 하다
 *     # y 오름차순, x 오름차순으로 정렬해서
 *       현재 좌표의 왼쪽, 오른쪽 좌표가 색깔이 같은지(y 좌표가 같은지) 확인한 후
 *       각 좌표까지의 거리를 구한 후 최소거리를 모두 더해주자
 *
 * Point
 * - 왼쪽, 오른쪽 좌표까지의 거리를 INF 로 초기화한 뒤,
 *   실제로 왼쪽, 오른쪽에 같은 색깔의 좌표가 있다면 그 거리를 구한다
 *   + l = 왼쪽 좌표까지의 거리, r = 오른쪽 좌표까지의 거리
 *     d = 화살표의 길이
 *     (l, r) = (a, b) -> d = min(a, b)
 *     (l, r) = (a, INF) -> d = min(a, INF) = a
 *     (l, r) = (INF, b) -> d = min(INF, b) = b
 *     (l, r) = (INF, INF) -> d = min(INF, INF) = INF
 *     # 왼쪽 또는 오른쪽에 같은 색깔의 좌표가 있다면 d 는 INF 가 아니다
 *       d 가 INF 라면 수평선 상에 같은 색깔의 다른점이 존재하지 않는 것이므로 0 으로 간주한다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define endl '\n'

// Set up : Global Variables
struct Point { int x, y; };

// Set up : Functions Declaration
bool operator < (Point u, Point v);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    vector<Point> P(N);
    for (int i=0; i<N; i++)
        cin >> P[i].x >> P[i].y;

    // Process
    sort(P.begin(), P.end());

    int INF = numeric_limits<int>::max();
    long ans = 0;
    for (int i=0; i<N; i++) {
        /* l = 왼쪽 좌표까지의 거리
         * r = 오른쪽 좌표까지의 거리
         * d = 화살표의 길이 */
        int l = INF, r = INF;
        /* 왼쪽에 같은 색깔의 좌표가 있다면 */
        if (i-1 >= 0 && P[i-1].y == P[i].y) {
            l = P[i].x - P[i-1].x;
        }
        /* 오른쪽에 같은 색깔의 좌표가 있다면 */
        if (i+1 < N && P[i+1].y == P[i].y) {
            r = P[i+1].x - P[i].x;
        }
        int d = min(l, r);
        /* 왼쪽 또는 오른쪽에 같은 색깔의 좌표가 있다면 */
        if (d != INF) ans += d;
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
bool operator < (Point u, Point v)
/* Point 구조체 정렬을 위한 함수 */
{
    /* y 좌표 오름차순, x 좌표 오름차순으로 정렬 */
    return make_pair(u.y, u.x) < make_pair(v.y, v.x);
}
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글