BOJ 2170번 선 긋기

BOJ : https://www.acmicpc.net/problem/2170

(다음은 같은 문제입니다. https://www.acmicpc.net/problem/15922)

github : https://github.com/junho0956/Algorithm/blob/master/2170/2170/%EC%86%8C%EC%8A%A4.cpp

 

라인스위핑과 관련된 문제라고 하는데

아직 라인스위핑에 대한 정확한 개념을 몰라서 생각나는대로 풀어봤습니다.

조만간 라인스위핑 알고리즘을 공부해서 정리하겠습니다.

 

선 긋기는 왼쪽부터 최대범위를 계속 갱신시켜주면서 전부 탐색하였습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef pair<int, int> pii;
int N;
 
vector<pii> v;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        int s, e;
        cin >> s >> e;
        v.push_back({ s,e });
    }
 
    sort(v.begin(), v.end());
 
    int s = v[0].first, e = v[0].second;
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int ns = v[i].first, ne = v[i].second;
        if (e < ns) {
            ans += (e - s);
            s = ns, e = ne;
        }
        else e = max(e, ne);
 
    }
    ans += e - s;
 
    cout << ans;
 
    return 0;
}