BOJ 2170 : 선 긋기

• 문제 링크 : boj.kr/2170
• 난이도 : G5
• 태그 : 정렬

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<pii> arr(n);
    for(auto &u : arr) cin >> u.first >> u.second;
    sort(all(arr));
    int ans = 0;
    int e = -INF;
    for(auto u : arr) {
        int temp = u.second - max(u.first, e);
        ans += max(temp, 0);
        e = max(e, u.second);
    }
    cout << ans;

    return 0;
}

---

풀이

선분을 시작 좌표를 기준으로 정렬한 결과를 $L= \{ l_1, l_2, \cdots, l_n \}, l_k = (s_k, e_k)$이라고 하자.

$s_{k+1}$는 $s_k$와 $e_k$ 의사이이거나 $e_k$보다 크다.

따라서 $l_{k+1}$의 선분이 추가될 때, 전체 선분의 길이는 $max(0, e_{k+1} - max(e_k, s_{k+1}))$만큼 추가된다.