[BOJ/백준 2170][C++] 선 긋기

문제

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

백준 2170

 

문제 내용

선분을 여러 개 입력받아, 선분끼리 이을 수 있는 것은 잇는다.

최종적으로 그려져있는 선들의 길이의 총합을 구하면 된다. (서로 이어진 선분은 하나의 선으로 생각한다)

 

문제 풀이

골드 5 문제이지만, 문제의 풀이 방법을 떠올리면 그렇게 어렵지 않다.

1. 먼저 선분들을 정렬한다.
(c++ sort 함수 쓰면, 선분의 시작이 증가하는 순으로 + 같을 경우 선분의 끝 지점이 증가하는 순으로 알아서 정렬해준다.)

2. 선분이 이어지는지를 체크한다
( 이전 선분의 끝 지점 >= 현재 선분의 시작 지점 )이면 두 선분은 이어진다고 볼 수 있다.
이 경우, 이전 선분의 끝 지점을 갱신해 주면 된다. (max 값으로 갱신해야 한다. (-5,5), (-3,2)와 같이 선분이 포함되는 경우도 있다)

3. 선분이 이어지지 않는다면 길이를 계산한다.
이전 선분과 현재 선분이 이어지지 않는다면, 그 뒤의 선분들 또한 이어지지 않는다. (정렬을 해뒀으니까)
그렇기 때문에 바로 길이를 계산해서 더해주면 된다.
+) 반복문이 끝나고 마지막으로 남아있는 선분의 길이를 계산해줘야 한다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;

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

    sort(arr.begin(),arr.end()); // first의 증가순으로, 같으면 second로 정렬

    int result=0; // 전체 길이 (최대 2*10^9)
    int start=arr[0].first;
    int end=arr[0].second;
    for(int i=1;i<n;i++){
        if(end>=arr[i].first){ //선분이 겹치거나 이어지면
            end=max(end, arr[i].second); //선분 연장
            
        }else{ // 겹치지 않는 경우 (end<arr[i].first)
            result+=(end-start);
            start=arr[i].first;
            end=arr[i].second;
        }
    }
    result+=(end-start);
    
    cout<<result;
}

 

문제 코드 설명

입출력 향상 코드를 추가하지 않으면 시간초과가 발생했다.

+) 결과 값의 길이가 최대 2*10^9까지 될 수 있는데, 이는 int 범위 내에 속하므로 long long을 쓸 필요는 없다.