[2170] 선 긋기

문제 링크 : https://www.acmicpc.net/problem/2170

2170 - 선 긋기

본문

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

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

입력

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

출력

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

제한

시간 제한	메모리 제한
1sec	192MB

---

풀이

뭔가 스택을 쌓고 합쳐가면서 계산해야할 것 같은 문제처럼 되어있지만, 사실 진짜 간단한 문제이다.

일단 각 선들의 길이의 전체 합은 답이 되지 않는다. 겹치는 부분이 있고, 정답에서는 그 겹치는 부분은 1번만 세어야하기 때문이다. 어느 부분이 겹치는 선들은 하나의 선으로 생각해도 길이의 차이가 생기지는 않는다. 따라서, 겹치는 부분의 선을 하나로 묶어서 계산하면 된다.

각 선은 시작지점과 끝점이 존재하므로, 한 점에 대해서 정렬해두면 다음 계산을 편하게 할 수 있다. 딱히 어느 점을 정해도 상관없으므로 선들을 시작점에 대해서 오름차순 정렬을 하자. 그리고 겹치는 부분에 대해서 하나의 선으로 생각해보도록 해보자.

현재 우리가 보고있는 선을 cur이라는 변수로 두자. 그리고, 다음으로 들어오는 선들이 cur과 겹칠 수 있는지 확인한다. 선들을 오름차순 정렬했으므로 다음으로 오는 선들은 시작점이 최소한 cur보다는 크거나 같다. 따라서 cur이 다른 선들보다 왼쪽에 존재한다. 그러면 두 선이 겹칠 수 있는 부분은 cur의 오른쪽 부분이 될 것이다. 즉, cur의 오른쪽 부분과 들어오는 선의 왼쪽이 겹치는지만 확인하면 된다. 겹친다면 cur을 업데이트해서 하나의 선처럼 생각하면 되고, 겹치지 않는다면 새로운 cur을 만듦과 동시에 기존 cur의 길이를 계산해주면 된다.

• 참고 알고리즘 :

코드

사용 언어 : C

최종 수정일 : 2023 / 3 / 27

#include <stdio.h>

typedef struct Node {
    int a, b;
} ND;

#define MAX_IDX 1000000
ND arr[MAX_IDX];
int n;

int cmp(ND* x, ND* y) {
    if (x->a == y->a) {
        return x->b > y->b;
    } else {
        return x->a > y->a;
    }
}

#define max(a, b) (((a) > (b)) ? (a) : (b))

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        arr[i] = (ND){a, b};
    }

    qsort(arr, n, sizeof(ND), cmp);

    ND cur = arr[0];
    int retval = 0;
    for (int i = 1; i < n; ++i) {
        if (cur.b >= arr[i].a) {
            cur.b = max(cur.b, arr[i].b);
        } else {
            retval += (cur.b - cur.a);
            cur = arr[i];
        }
    }

    retval += (cur.b - cur.a);
    printf("%d", retval);
    return 0;
}

• cur : 현재 계산 중인 선을 기록. 겹치지 않는 선이 주어진다면 독립시키고 길이를 잼