[BOJ 2170]

문제 바로가기 : https://www.acmicpc.net/problem/2170
문제 설명은 위 링크에서 확인해주시길 바랍니다.

solution

review

선을 그었을 때 길이가 몇인지 출력하는 문제다. 겹치는 구간은 더하지 않도록 해야 한다.
처음에 읽으면서 배열쓰면 될거같다는 생각을 했는데 범위가 -10억부터 10억까지 무시무시하다.
그래서 각 값을 pair로 담아 그때그때 계산해주는 방식을 택했다.
나는 자료형을 long long으로 했는데 int를 써도 문제 없다. 최대 길이는 20억인데 int 범위를 초과하지 않아서 그렇다.

겹치는 구간을 어떻게 해야 무시하고 안겹치는 부분을 더할 수 있을까?
배열을 안쓰기 때문에 구간을 표시해놓으면서 값을 구하는건 의미가 없다. 메모리뿐만 아니라 시간도 문제가 된다.
구간이 시작하는 값을 기준으로 오름차순으로 정렬하면 값을 구하기가 한결 편해진다.
케이스는 3가지가 생긴다. 아예 겹치거나, 일부 겹치거나, 아예 안겹치거나.
전부 혹은 일부가 겹치면 현재 구간을 재설정 해준다. 그러나 답에는 아직 반영하지 않는다.

안겹치는 경우 현재 구간을 재설정해주고 답을 갱신한다.
마지막(i==n-1)은 답 갱신이 안되므로 for문 밖에서 한번 더 해주자.

ll left = -INF, right = -INF, ans = 0;
    for (int i = 0; i < n; i++) {
      //안겹치는 경우
      if (right < lines[i].first) {
          ans += right - left;
          left = lines[i].first;
          right = lines[i].second;
      }
      //겹치는 경우
      else {
        right = max(right, lines[i].second);
    }
}
ans += right - left;