[구현 / BOJ 2170 / C++] 선긋기

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

2170번: 선 긋기

 

이 문제는 어렵게 접근하면 한도 끝도 없이 어려워진다..

 

단순하게 시각화해서 문제를 해결해보자!

 

우선 도화지에 선분을 그어보자.

최종적으로 겹치는 곳을 제외한 선분의 합만 구하면 끝이다!

 

즉, 우리가 주목해야할 것은 시작점과 끝점이다.

만약 새로 그은 선분의 시작점(ns)이 원래 그어져있는 시작점(bs)과 끝점(be) 사이에 있고, 

새로 그은 선분의 끝점(ne)이 원래 그어져 있는 끝점(be)보다 멀리 있다면,

 

선분의 총 길이는 ne에서 bs를 뺀 값이 된다.

 

이것을 응용해서 해결해보자!

 

#include <bits/stdc++.h>

using namespace std;

long long n, x, y, res, bs, be;
vector<pair<long long, long long>> v;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    while(n--){
        cin >> x >> y;
        v.push_back({x, y});
    }
    
    sort(v.begin(), v.end());
    
    bs = v[0].first;
    be = v[0].second;
    
    for(auto i : v){
        long long ns = i.first;
        long long ne = i.second;
        
        if(bs <= ns && ns <= be && be <= ne){ // bs x be y 일때
            be = ne; // 끝점 업데이트
        }else if (be <= ns){ // bs be x y일때
            res += (be-bs);
            bs=ns;
            be=ne;
        }
        
    }
    
    res+=be-bs;
    
    cout << res << "\n";
    
}