백준 g5 2170 선 긋기 c++

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

2170번: 선 긋기

 

문제 설명

• 선을 x~y까지 N개 그을 수 있다. 그어진 선 길이의 총합 구하기
  • 단, 겹쳐진 선은 구분할 수 없다.

풀이

 

시작점을 기준으로 정렬을 하고, 만약 겹치는 구간이 있다면 포함시키면서 한 덩어리(?)를 확장시켜 나간다. 겹치는 구간이 끝나면 이미 정렬된 상태니까 그 덩어리는 끝난 것이므로 새로운 선에서 다시 시작한다.

 

처음에는 강의실 문제처럼 끝 점을 기준으로 했었는데, 이 경우엔 16 23 45라는 반례가 있다. 즉, 시작점을 기준으로 해야 저런 짜잘한 선들도 모두 포함시킬 수 있다.

 

수도 코드

    for i = 1 ~ N-1
        ns = arr[i].first;
        ne = arr[i].second;
        if 다음 start < 현재 덩어리의 end
            start = min(start, ns) // start, end 점 확장
            end = max(end, ne)
        } else { // 이전 구간이랑 안 겹침, 겹치는 구간 끝나서 더해줌, ns == end 인 경우도 포함
            ans += end - start;
            start = ns;
            end = ne;
        }
    }
    
    맨 마지막 덩어리도 더해줌
    ans += end - start

 

 

전체 코드

/*boj g5 2170 선 긋기*/
#include <algorithm>
#include <iostream>
#define MAXN 1000010
using namespace std;

int N;
pair<int, int> arr[MAXN];
long long ans = 0;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        arr[i] = make_pair(x, y); // 끝 점 기준으로 오름차순
    }
    long long ns, ne;
    long long start;
    long long end;

    sort(arr, arr + N);
    start = arr[0].first;
    end = arr[0].second;

    for (int i = 1; i < N; i++) {
        ns = arr[i].first;
        ne = arr[i].second;
        if (ns < end) { // 다음 start < end 이면 겹침
            start = min(start, ns);
            end = max(end, ne);
        } else { // 이전 구간이랑 안 겹침, 겹치는 구간 끝나서 더해줌, ns == end 인 경우도 포함
            ans += end - start;
            start = ns;
            end = ne;
        }
    }
    ans += end - start;
    cout << ans << "\n";
}