[백준/C++] 알고리즘 2170번 - 선 긋기

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 2170번 - 선 긋기를 풀어보도록 하겠습니다.

 

 

 

 

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

 

[문제 접근]

N은 백만이하, 시간 제한 1초이기 때문에, O(N^2)은 불가능합니다.

그래서 for문 하나로 끝내야한다는 생각을 했습니다. 

한편, 이 문제의 핵심은 겹치는 곳이었습니다.

최대한 저장을 하지 않기 위해 이전 시작점, 이전 끝점, 현재 시작점, 현재 끝점만을 이용했습니다.

 

[풀이 전략]

1. 입력값들을 시작점을 기준으로 오름차순 정렬을 진행했습니다.

2. prest, preen은 첫번째 입력값으로 초기화했습니다.

3. for문을 이용하여 curst, curen과 prest와 preen을 비교하여 업데이트를 해주었습니다.

- preen보다 curst가 크거나 같으면 pre의 길이를 구해서 result에 더하고, prest와 preen을 현재 입력값으로 업데이트 합니다.

- 그렇지 않으면 이전 시작점과 현재 시작점 중 작은 시작점을 이전 시작점으로, 이전 끝점과 현재 끝점 중 큰 끝점을 이전 끝점으로 업데이트합니다.

4. 마지막 pre의 길이를 result에 더합니다.

5. result 출력합니다.

 

[코드]

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



int n ; 
vector<pair<long long ,long long>> v ;
long long result ; 

int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n ;
    for(int i = 0 ; i < n ; i++){
        int st, en ;
        cin >> st >> en ; 
        v.push_back({st,en});
    }
    sort(v.begin(),v.end());

    long long prest = v[0].first;
    long long preen = v[0].second;

    for(int i = 1 ; i < n ; i++){
        long long curst = v[i].first;
        long long curen = v[i].second;

        if(preen <= curst) {
            result += preen - prest ;
            prest = curst ;
            preen = curen;

        } else {
            prest = min(prest, curst);
            preen = max(preen,curen);
        }
    }

    result += preen - prest ;

    cout << result ; 

}

 

[배울 점]

- 정렬의 시간복잡도는 O(N)이기 때문에 필요하다면 두려워말고 사용하기