[백준 2170번] 선 긋기 (C++)

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

2170번: 선 긋기

---

선 긋기 문제는 그리드 알고리즘으로 해결할 수 있습니다.

 

두 선 Line1, Line2이 아래 3가지 조건을 모두 만족할 때 겹쳐있다고 할 수 있습니다. 그렇지 않으면 겹치지 않은 것입니다. 

(단, start는 선의 시작점, end는 끝점)

• Line1.start <= Line2.start 
• Line1.end >= Line2.start
• Line1.end <= Line2.end

따라서 입력 받은 선들을 시작점을 기준으로 정렬한 후,

겹치지 않는 선을 만날 때까지 선을 늘려준 후, 겹치지 않는 선을 만나면, 현재 선의 길이를 더해주는 것을 반복해주면됩니다. 

 

아래는 전체 코드입니다.

 

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

typedef struct{
    int start, end;
}line;
line lines[1000010];

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

    int n; cin >> n;
    for(int i = 0; i < n; i++)
        cin >> lines[i].start >> lines[i].end;  //  선들의 정보 입력 받음

    sort(lines, lines + n, [](line a, line b) -> bool {return a.start < b.start;}); // 시작점을 기준으로 정렬

    int ans = 0;
    line cur = {(INT_MIN), INT_MIN};    // 현재 선의 정보
    for(auto line : lines){ // 각 선에 대해 반복
        if(cur.end >= line.start && cur.end < line.end){    // 겹치는 경우
            cur.end = line.end; // 현재 선의 끝점을 업데이트
        }else if(cur.end < line.start){ // 겹치지 않는 선을 만나면
            ans += cur.end - cur.start; // 현재 선의 길이를 더해줌
            cur = line; // 겹치지 않는 선으로 업데이트
        }
    }
    ans += cur.end - cur.start; // 마지막 선의 길이 더해줌
    cout << ans << "\n";
}