BOJ 2170번: 선 긋기

문제 설명

두 점 위치가 주어지고, 선의 총 길이 구하기 (겹치는 부분은 중복으로 세지 않음)

🔗 문제 링크

핵심 아이디어

• x와 y를 pair로 입력받아서 오름차순 정렬
• pair들을 순회하면서 겹치는 부분이 있으면 start와 end 값에 누적하고, 겹치는 부분이 없으면 새로운 start와 end 값으로 시작
• 맨 끝에 남은 부분 꼭 더하기!

코드

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n; cin >> n;
    vector<pair<int,int>> v(n);
    long long ans = 0;
    for(int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
    
    sort(v.begin(), v.end());
    
    int start = v[0].first;
    int end = v[0].second;
    
    for(int i = 1; i < n; i++){
        if (v[i].first <= end){ // 겹치는 부분이 있음
            end = max(end, v[i].second);
        }
        else{ // 겹치는 부분이 없음
            ans += (end - start);
            start = v[i].first;
            end = v[i].second;
        }
    }
    
    ans += (end - start); // 맨 마지막에 남은 부분 반영
    cout << ans;
}

‼️ 놓친 부분

• ❌ 20억짜리 배열 만들어서 안 겹치는 부분 카운트할까 생각했지만.. 시간도 오래 걸리고 범위도 너무 크다!
• ✅ 시작과 끝 이렇게 2가지 값만 갱신하는 법을 생각해보자..