(C++) - 백준(BOJ) 2170번 : 선 긋기

www.acmicpc.net/problem/2170

2170번: 선 긋기

sweeping문제였습니다.

*c와 동기화를 끊지 않으면 시간초과가 나는데 이유를 잘 모르겠습니다. 아시는 분은 댓글 달아주시면 감사하겠습니다. ㅠㅠ

풀이방법

 1. vector pair<int,int> 자료구조인 point라는 변수에 x,y값을 n번만큼 입력받습니다.

 

 2. first를 기준으로 오름차순 first가 같다면 second 기준으로 오름차순 정렬해줍니다. 그 후 startPoint는 가장 작은 점의 x좌표, endPoint는 y좌표로 선언 후 값을 저장해줍니다.

 

 3. 정렬된 point를 모두 확인하면서 나아갑니다.

   3-1. 만약 선분이 안겹친다면 기존에 확인해줬던 startPoint에서 endPoint까지의 거리를 더해줍니다. 그 후 해당 값들을 현재 x,y로 갱신해줍니다.

 

  3-2. 선분이 겹친다면 endPoint를 갱신해줍니다. 갱신해줄 때 현재 y점이 커야됩니다.

 

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
using pii = pair<int,int>;
int n, ans, startPoint, endPoint;

int main(){
    fastio;
    cin >> n;
    vector <pii> point(n);
    for(auto &p : point) cin >> p.first >> p.second;
    sort(point.begin(),point.end());
    startPoint = point[0].first;
    endPoint = point[0].second;
    for(int i = 1; i < n; i++){
        if(endPoint < point[i].first){ //선 안겹치는 경우
            ans += endPoint - startPoint;
            startPoint = point[i].first;
            endPoint = point[i].second;
        }
        else endPoint = max(endPoint,point[i].second); //선 겹치는 경우
    }
    ans += endPoint - startPoint;
    cout << ans << '\n';
}