[C++][백준 2170] 선 긋기

문제

접근 방법

처음에 입력으로 x, y를 준다고 하여 2차원 공간인 줄 알았다. 하지만 그냥 변수 이름이 x, y였던 것이다...
여러 번 그은 곳이란 건 겹치는 경우를 말하는 것 같았다. 그렇다면 끝점만 늘려주면 될 것 같았다. 추가로 순서대로 입력된다는 말이 없으므로 정렬도 돌려주었다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 101
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, ret = 0;
    vector<pair<int, int>> v;
    cin >> N;
    while (N--)
    {
        int x, y;
        cin >> x >> y;
        v.push_back({x, y});
    }
    sort(v.begin(), v.end());
    int left = v[0].first, right = v[0].second;
    for (auto i : v)
    {
        if (right < i.first) // 겹치지 않는 경우 (새로운 선의 시작점이 기존 선의 끝점보다 클 경우)
        {
            ret += right - left; // 기존 선의 길이를 답에 추가해준다.
            left = i.first;      // 새로운 선의 시작과 끝으로 바꾸어준다.
            right = i.second;
        }
        else // 겹치는 선일 경우 (새로운 선의 시작점이 기존 선의 끝점보다 작거나 같을 경우)
        {
            if (right < i.second) // 새로운 선의 끝점이 더 클 시 끝점만 늘려준다.
                right = i.second;
        }
    }
    ret += right - left; // 모든 선을 소비했을 때 마지막 남은 선의 길이
    cout << ret;
    return 0;
}

풀이

선이 순서대로 제공된다는 보장이 없으므로 정렬하였다.
겹치는 경우 새로운 선의 끝점이 더 클 경우 기존의 선이 길어지지만 짧으면 무시하면 된다. (겹칠 뿐 길이에는 영향을 주지 못한다)
겹치지 않는 경우 기존 선과 겹칠 일이 없으므로 (시작점 순서대로 정렬됐으므로) 기존 선의 길이를 정답에 더해주고 새로운 선으로 교체한다.
이것을 반복하고 난 뒤 마지막에는 처리되지 못한 현재 선에 길이를 더해주면 된다.

그리디인 줄 알았는데 스위핑이라고 한다. 스위핑 들어본 거 같으면서도 처음 보는 느낌이다. 스위핑이란 정렬된 순서대로 문제를 처리하는 것이라고 한다.

결국 회의실 배정도 스위핑으로 푼 것인가? 정의대로라면 그렇다고 볼 수 있는 것 같다.