BOJ 2170 - 선긋기

www.acmicpc.net/problem/2170

2170번: 선 긋기

 

입력으로 들어온 시작점, 끝점을 전부 하나의 자료형에 담아둔 뒤,

시작점 기준으로 오름차순 정렬한다.

그 후 정렬된 배열에서

첫번째 원소는 가장 앞에 있는 시작점 이므로, 이 좌표를 기준으로 삼고

다음 좌표와 비교할때, 이전 좌표의 시작점 끝점 사이에 존재하는 선인가? (겹치는 선인가) 판별한다

그리고 겹치는 선이면서 동시에 다음 좌표의 끝점이 더 긴 경우 끝점을 그 값으로 갱신한다.

그렇지 않으면 끊긴선이므로, 별도의 선으로 길이를 계산한다. 

 

 

- c++

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
int N, answer;
vector<pair<int, int>> vec;
 
bool comp(pair<int, int> p1, pair<int, int> p2) {
    return p1.first < p2.first;
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
 
    cin >> N;
    
    for (int i = 0; i < N; ++i) {
        int start, end;
        cin >> start >> end;
        vec.push_back({start, end});
    }
    
    sort(vec.begin(), vec.end(), comp);
    
    int start = vec[0].first, end = vec[0].second;
    for (int i = 1; i < vec.size(); ++i) {
        if (start <= vec[i].first && vec[i].first <= end && end < vec[i].second) {
            end = vec[i].second; 
        } else if (vec[i].first > end) {
            answer += (end - start);
            start = vec[i].first;
            end = vec[i].second;
        }
    }
    
    answer += (end - start);
    cout << answer;
    
    return 0;
}

 

 

 

 

대표적인 스위핑 문제이다.

아래의 사이트 참조

blog.naver.com/kks227/220907708368

스위핑 기법(Sweeping Algorithm) (수정: 2019-06-24)