BOJ #15922

---

LEVEL :

Gold5

---

문제 요약 :

주어진 선분을 이었을 때, 형성되는 선분의 길이를 구하여라. 선분 겹침 가능.

---

해결 방안 :

솔직히 골드5문제는 아닌것 같다. 너무 간단한 메커니즘이었다.
만약 x좌표가 정렬 되어 주어진게 아니라면 그나마 조금 더 어려울 수 있었을 듯 하다.
현재 선분을 시작으로 다음으로 주어진 선분이 현재 선분에 겹치는지 아닌지만 따져주면된다. 겹치면 현재선분이 더 긴 선분으로 연장 되는지 아닌지만 확인하면서 현재 선분을 수정해 간다. 만약 겹치지 않는다면, 진행 되고 있던 현재선분의 길이를 sum에 추가하고, 새로운 선분을 현재선분으로 이어나간다.
코드를 보면 위의 설명을 쉽게 이해 할 수 있을 것이다.

---

시간 복잡도 :

시간 복잡도는 O(N)으로 해결 할 수 있는 문제였다.

---

Solution

import sys
input = sys.stdin.readline
if __name__ == "__main__" :
    n = int(input().strip())
    lines = [list(map(int,input().strip().split())) for _ in range(n)]
    length = 0
    cur = lines[0]
    for line in lines :
        if cur[1] > line[0] :
            cur[1] = max(cur[1],line[1])
        else :
            length += cur[1] - cur[0]
            cur = line
    length += cur[1] - cur[0]
    print(length)