[BOJ/백준][Gold5] 2170 : 선 긋기 (C++)

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

2170번: 선 긋기

 

 

[난이도] Gold5
[유형] 스위핑

[풀이]
1. pair 배열 에 (시작점,끝점)으로 저장 뒤 시작점을 기준으로 오름차순 정렬한다.
2. s:현재 긋고 있는 선의 시작점, e:현재 긋고 있는 선의 끝점
3. 앞에서부터 pair 의 선들을 확인하면서 선이 s~e에 포함되면 skip, 선의 앞이 e보다 작거나 같고 뒤가 e보다 큰 경우
e를 업데이트, 선의 앞이 e보다 크면 e-s를 답에 저장하고 s,e를 새로 업데이트.

위 방식으로 누적된 길이가 그리는 선의 최종 길이이다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int N;
pair<int,int> a[1000000];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d%d",&a[i].first,&a[i].second);
    
    sort(a,a+N); 
    int s=a[0].first,e=a[0].second;
    int d=0;
    for(int i=1;i<N;i++){
        if(a[i].first<=e) {
            if(e<a[i].second) e=a[i].second;
        }
        else {
            d+=e-s;
            s=a[i].first;
            e=a[i].second;
        } 
    }
    d+=e-s;
    printf("%d",d);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2170.cpp