백준 2170번 [선 긋기](C++) -yes6686- 티스토리

백준 문제 풀이: 2170 (선 긋기)

---

문제 링크: https://www.acmicpc.net/problem/2170

문제 설명:

좌표 평면 위에 n개의 선분이 주어집니다. 각각의 선분은 x축 위에서 시작점과 끝점을 가지며, 이 선분들이 겹치는 경우 중복을 제거한 실제 총 선 길이를 구하는 문제입니다.

이 문제는 선분을 시작점을 기준으로 정렬한 뒤, 현재 선분이 이전 선분과 겹치는지를 판단하여 겹치지 않으면 누적 길이를 더하고, 겹치면 끝점을 갱신하는 방식으로 해결할 수 있습니다.

---

문제 해결 코드

// 선 긋기 (정렬 후 누적합)
#include <iostream>
#include <algorithm>
using namespace std;

pair<int, int> arr[1000001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i].first >> arr[i].second;
    }

    sort(arr, arr + n);  // 시작점을 기준으로 정렬

    int s = arr[0].first;
    int e = arr[0].second;
    int ans = 0;

    for (int i = 1; i < n; i++) {
        if (e <= arr[i].first) {
            // 현재 선분이 겹치지 않으면 누적 길이 더하기
            ans += (e - s);
            s = arr[i].first;
            e = arr[i].second;
        } else {
            // 겹친다면 끝점만 갱신
            e = max(e, arr[i].second);
        }
    }

    ans += (e - s);  // 마지막 구간 누적
    cout << ans << '\n';
}

---

코드 설명

• 핵심 알고리즘: 정렬 + 스위핑(Sweep Line). 선분들을 정렬한 후, 겹치는 부분을 하나로 합쳐 누적합을 구합니다.
• 구현 세부사항: 선분을 정렬한 뒤, 현재 선분이 이전 선분의 범위 안에 있다면 끝점을 확장합니다. 겹치지 않으면 현재까지의 길이를 더하고 새롭게 시작합니다.
• 시간 복잡도 분석: 정렬 O(n log n), 이후 선형 탐색 O(n)으로 전체 시간 복잡도는 O(n log n)입니다.

---

결과

전체 선분에서 중복 없이 덮는 길이를 출력합니다.

예시 입력:

4
1 3
2 5
6 8
7 9

예시 출력:

7

다른 풀이 방식이나 개선 아이디어가 있다면 댓글로 공유해주세요!