백준 2170번 선 긋기 - C++ 풀이

---

 

1. 선분들을 시작점 오름차순으로 정렬한다.
2. 스위핑하면서 모든 선분의 길이를 더한다.

 

1. 선분들을 시작점 오름차순으로 정렬한다.

 스위핑을 통해 해결할 수 있는 문제이다. 왼쪽부터 스위핑하면서 선분의 총 길이를 계산해줄 것이다. 이 작업을 위해 먼저 주어진 선분들을 시작점 오름차순으로 정렬한다.

 

2. 스위핑하면서 모든 선분의 길이를 더한다.

 이제 왼쪽부터 스위핑하면서 모든 선분의 길이를 더한다. 중간에 겹치는 선분들을 하나의 선분으로 만들어주면서 이동해주면 된다. 현재 처리중인 선분의 시작점과 끝점 좌표를 각각 s, e, 다음 선분의 시작점과 끝점 과표를 각각 ns, ne라고 하자. 시작점 오름차순으로 정렬해주었기 때문에 s ≤ ns임은 보장되어 있다. 따라서 ns < e 이면, 현재 선분과 다음 선분이 겹친다는 의미이므로 e = max(e, ne)로 현재 선분과 다음 선분을 합쳐준다. 반대로 e < ns 이면 현재 선분과 다음 선분이 겹치지 않으므로, 현재 선분의 길이를 더해주고 s=ns, e=ne로 새 선분을 시작하면 된다.

 

반응형

---

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

using namespace std;
typedef pair<int, int> pii;

int N;
vector<pii> lines;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i=0; i<N; i++) {
        int s, e;
        cin >> s >> e;
        lines.push_back({s, e});
    }
    
    sort(lines.begin(), lines.end());
    
    int s = -1e9, e = -1e9;         // 현재 선분
    int len = 0;
    
    for (int i=0; i<N; i++) {
        if (lines[i].first > e) {   // 새 선분 시작
            len += e-s;
            s = lines[i].first;
            e = lines[i].second;
        }
        else {                      // 기존 선분 연장
            e = max(e, lines[i].second);
        }
    }
    len += e-s;
    
    cout << len;

    return 0;
}