[백준][스위핑] 2170 선 긋기 c++구현

목차

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

문제

 

문제 구현 아이디어

두 점의 범위가 억이 넘어가므로 일단 공간 복잡도상으로 배열은 사용하지 못한다는 것을 알 수 있다.

따라서 갱신을 하며 누적해주는 식으로 풀었다.

 

 

코드 구현

#include <iostream>
#include <vector>
#include<map>
#include<math.h>
#include <algorithm>
typedef long long ll;

using namespace std;

vector<pair< ll, ll>>v;

ll N, x, y;
ll total = 0;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0); 
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> x >> y;
        v.push_back({ x, y });
    }
    sort(v.begin(), v.end());

    ll front = v[0].first;
    ll back = v[0].second;
    for (int i = 1; i < v.size(); i++) {
        if (back < v[i].first) {
            total += back - front;
            back = v[i].second;
            front = v[i].first;
        }
        else if (back >= v[i].first && back <= v[i].second) {
            back = v[i].second;
        }
    }
    total += back - front;
    cout << total;
    
    return 0;
}