(2170) 선 긋기

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

단계별로 풀어보기

49단계(스위핑) 1번째

 

 

 

스위핑은 영단어 Sweeping(쓸다)에서 유래된 말에서 알 수 있듯 한 쪽에서 다른 쪽으로 쓸듯이 진행하는 과정이나 그렇게 푸는 방식을 의미한다.

문제에서 주어진 선분을 전부 시작점을 기준으로 오름차순으로 정렬한다. 첫 선분을 기준으로 하는 선분을 만들고, 다음 선분의 시작점이 기준 선분과 겹친다면(right보다 크지 않다면) 다음 선분이나 기준 선분을 합친 새로운 기준 선분이 있다고 가정할 수 있다. 만약 다음 선분의 시작점이 기준 선분과 겹치지 않는다면 기준 선분의 길이를 더하고 다음 선분을 새로운 기준 선분으로 설정한다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 1000000001

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<pair<int,int>> v(n);
  
  for(int i=0;i<n;i++)  cin >> v[i].first >> v[i].second;
  
  sort(v.begin(), v.end());
  
  int left= -INF, right= -INF, ans= 0;
  
  for(auto line:v){
    if(line.first<=right){
      right= max(right, line.second);
    }else{
      ans+= right-left;
      
      left= line.first;
      right= line.second;
    }
  }
  ans+= right-left;
  
  cout << ans;
  
  return 0;
}