[백준][C++] 2170 선 긋기

www.acmicpc.net/problem/2170

2170번: 선 긋기

 

 

 

알고리즘 종류

스위핑

 

 

사고 과정

시작점을 기준으로 오름차순 정렬합니다. 그리고 선을 그을 때 3가지의 경우가 나옵니다.

 

1. 이전 선에 모두 포함되는 경우

 

2. 이전 선에 일부만 포함되는 경우

 

3. 이전 선에 포함되지 않는 경우

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
typedef long long ll;
 
int n;
 
vector<pair<ll, ll> > v;
 
 
bool cmp(pair<ll, ll> a, pair<ll, ll> b){
    if(a.first != b.first) return a.first < b.first;
    return a.second < b.second;
}
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    
    ll a, b;
    for(int i=0; i<n; i++){
        cin >> a >> b;
        v.push_back({a, b});
    }
    
    sort(v.begin(), v.end(), cmp);
    
    ll s = v[0].first;
    ll e = v[0].second;
    ll ans = (e - s);
    
    for(int i=1; i<v.size(); i++){
        
        ll ns = v[i].first;
        ll ne = v[i].second;
        
        if(s <= ns && ne <= e) continue;
        
        if(ns <= e && e <= ne){
            ans += (ne - e);
            e = ne;
        }
        
        if(e < ns){
            s = ns;
            e = ne;
            ans += (ne - ns);
        }
        
    }
    
    cout << ans << endl;
}

 

 

 

시행착오