[Bronze I] 16396번 - 선 그리기

 

[문제 위치]

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

[문제 풀이]

이 문제는 여러 선분이 주어졌을 때, 중복되지 않는 총 길이를 구하는 문제입니다. 각 선분은 시작점과 끝점으로 정의됩니다. 주어진 선분들이 겹치는 부분을 고려하여 총 길이를 구하는 것이 핵심입니다.

접근 방식:

1. 선분의 시작점을 기준으로 정렬합니다.
2. 정렬된 선분들을 순차적으로 확인하며, 현재 선분이 이전 선분과 겹치는지 확인합니다.
3. 겹치는 경우 끝점을 확장하여 합병합니다.
4. 비겹치는 새로운 선분이 시작되면, 이전 선분의 길이를 총 길이에 더하고 새로운 선분으로 갱신합니다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<pair<int, int>> lines(N);

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

    // 시작점을 기준으로 정렬
    sort(lines.begin(), lines.end());

    int total_length = 0;
    int start = lines[0].first;
    int end = lines[0].second;

    for (int i = 1; i < N; ++i) {
        if (lines[i].first <= end) {
            // 현재 선분이 이전 선분과 겹침
            end = max(end, lines[i].second);
        } else {
            // 새로운 비겹치는 선분 시작
            total_length += end - start;
            start = lines[i].first;
            end = lines[i].second;
        }
    }
    
    // 마지막 선분 길이 추가
    total_length += end - start;

    cout << total_length << endl;
    return 0;
}