[백준 2170번] 선 긋기 (C++)

문제링크 : https://www.acmicpc.net/problem/2170

2170번: 선 긋기

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

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

    int N, length = 0, S, E;
    cin >> N;

    vector<pii> xy;
    for(int i=0; i<N; i++)
    {
        int x, y;
        cin >> x >> y;
        xy.push_back({x,y});
    }

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

    S = xy[0].first; 
    E = xy[0].second; 

    for(int i=1; i<N; i++)
    {   
        if(E < xy[i].first)  //새 선분
        {
            length += (E - S);  //그전까지 그은 선분 정리
            S = xy[i].first;
        }

        if(E < xy[i].second) //선분 확장
        {
            E = xy[i].second;
        }
    }
    length += (E - S); //마지막 선분 정리

    cout << length;

    return 0;

}

스위핑 알고리즘의 기본문제다.

스위핑 알고리즘이 뭔지 몰라도 푸는데에는 지장이 없을 것 같다.

 

뒤에 오는 선분의 End가 기존 End보다 크다면 End를 갱신하여 선분의 길이를 늘리고,

뒤에 오는 선분의 Start가 기존 End보다 크다면 아에 겹치지 않으므로 Start를 갱신하여 새 선분을 만든다.

이때 기존까지의 선분 길이를 저장한다.

 

 뒤에 오는 선분이 기존 선분 길이 안에 완전히 겹치는 경우는 선분의 길이가 변하지 않으므로 갱신할 값이 없다.