[BOJ/백준][Gold5] 15922 : 아우으 우아으이야!! (C++)

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

15922번: 아우으 우아으이야!!

 

 

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

[풀이]
pair 배열에 (시작점,끝점)을 넣어둔 뒤, 시작점을 기준으로 오름차순을 해줍니다.
그 뒤에 스위핑을 이용하여 겹치는 부분을 처리해서 하나의 선분으로 묶어주면
전체 길이를 쉽게 구할 수 있습니다.

 

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

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