[백준 2170] 선 긋기

0. 제목

• 백준 2170 선 긋기
• BOJ 2170 선 긋기
• C++ 2170 선 긋기

---

1. 문제

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

---

2. 풀이

• 먼저 from, to N쌍을 입력받는다.
• 그 후 from을 기준으로 정렬을 한다.
• 그럼 선끼리 겹치는 선들이 있을 것이고 겹치지 않는 선들이 있을 것이다.
• 겹치지 않는 경우에는 현재 길이에 l-r 만큼 더해주면 되고 겹치는 경우에는 오른쪽 끝을 다음 번 오른쪽 끝으로 갱신시켜주면 된다.
• 반복문이 끝난 후에는 마지막으로 갱신된 l-r을 더해주면 답이 나온다.
• 주의할 점은 이 문제에서 N과 선택한 지점의 범위가 크다. 따라서 main함수의 첫 세줄을 추가 하지 않았을 때는 시간초과로 떴다.
• 저 세줄을 추가하면 정답처리가 된다.

---

3. 코드

#include <iostream>
#include <algorithm>
using namespace std;
 
typedef pair<int, int> P;
P L[1000001];
int N;
int from, to;
int l, r;
int ans = 0;
 
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> from >> to;
        L[i] = P(from, to);
    }
    sort(L, L+N);
    l = L[0].first;
    r = L[0].second;
    
    for(int i = 1; i < N; i++){
        if(L[i].first > r){//안겹치는 경우
            ans += r-l;
            l = L[i].first;
            r = L[i].second;
        }
        else if(L[i].first < r && L[i].second > r){//겹치는 경우
            r = L[i].second;
        }
    }
    ans += r-l;
    
    cout << ans << '\n';
    
    return 0;
}