[C++] 2170 - 선 긋기 (골드5)

1. 문제 설명

 

2170번: 선 긋기

 

---

2. 아이디어

 

스와핑 관련 문제를 처음 봐서 찾아봤었다.

그렇게 어려운 로직이 아니었다.

일단 값을 입력받고 시작점 기준으로 정렬을 한 번 수행한다.

 

그 뒤로 길이를 체크해줄 left와 right 변수를 -INF로 설정해주고 right와 시작점을 비교한다.

시작점이 현재 right의 위치보다 작다면 right의 값을 끝점으로 옮길 것이지만,

그게 아니라면 입력받은 right와 left의 차이만큼 결과값에 저장하고 left와 right 각각에

시작점과 끝점을 할당하는 방식으로 돌아간다. 

 

시작점을 기준으로 정렬되어 있는 상태이기 때문에 만약 중첩되는 선분의 경우

right값이 갱신되면서 가장 긴 선분의 길이 한 번만 체크하게 되는 원리다.

 

---

3. 코드

#include <iostream>
#include <algorithm>

using namespace std;
typedef pair<int, int> p;
const int INF = 1e9;

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

    p arr[1000000];
    for (int i=0; i<n; i++) {
        int x, y; cin >> x >> y;
        arr[i].first = x; arr[i].second = y;
    }
    sort(arr, arr+n);

    int left = -INF, right = -INF, answer=0;

    for (int i=0; i<n; i++) {
        if (arr[i].first < right) {
            right = max(right, arr[i].second);
        } else {
            answer += right - left;
            left = arr[i].first;
            right = arr[i].second;
        }
    }
    answer += right - left;

    cout << answer << endl;

    return 0;
}