[백준]2170번 선 긋기 - C++

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

2170번: 선 긋기

문제

매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.

이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.

입력

첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.

출력

첫째 줄에 그은 선의 총 길이를 출력한다.

---

예제가 잘 주어져 있다. 이런 문제는 정렬을 하여 왼쪽부터 오른쪽으로 훑어 가는 것이 좋아 보인다.

1~ 3 이 그어져 있을 때 2 ~ 5를 긋는다면 1~5를 긋는다고 생각할 수 있다.

1~5 가 그어져 있을 때 6 ~ 7을 긋는 다면 별도로 생각해야 한다.

따라서 현재까지 그어져 있는 줄의 최댓값보다 새로 들어온 줄의 시작 값이 크다면 현재까지 길이를 저장하고 새로운 시작~끝을 기록한다.

만약 현재까지 그어져 있는 줄보다 시작값이 작다면 새로 들어온 값의 끝 값을 봐야 한다. 끝 값이 현재 끝 값보다 작다면 새로 그은 선이 없는 것이므로 넘어간다. 끝값이 현재 끝 값보다 크다면 현재 끝 값을 최신화한다.

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

using namespace std;

typedef pair<int,int> point;

int N,x,y;
point arr[1000001];

int main (){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    for(int i = 0 ; i < N ; i++){
        cin >> x >> y;
        arr[i] = make_pair(x,y);
    }
    sort(arr, arr + N);
    
    int cur_s,cur_e,ans=0;
    cur_s = arr[0].first;
    cur_e = arr[0].second;
    for(int i = 1 ; i < N ; i++){
        if(cur_e >= arr[i].first ){
            if(cur_e < arr[i].second)
                cur_e = arr[i].second;
        }
        else{
            ans += cur_e - cur_s;
            cur_s = arr[i].first;
            cur_e = arr[i].second;
        }
    }
    ans += cur_e - cur_s;
    cout << ans;
}

---

처음에 제출하였을 때 틀렸습니다가 나왔다. 고민을 해보았지만 맞게 짠 것 같아 다른 코드를 참조한 결과 현재 끝 값이 새로 들어온 끝 값보다 클 수 있다는 사실을 파악하지 못해서였다. 이를 고치니 시간 초과가 났다. 다른 코드와 비교를 하였지만 다른 점이 없었다. 알고 보니 tie()를 처리해주지 않아서였다. 딱히 넣지 않아도 다른 문제들이 시간 초과가 나지 않아 평소에 추가를 안 했는데 딱 걸려버렸다!!