[BOJ] 백준 2170번 선 긋기

백준 2170번 선 긋기 (골드4)

문제

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

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

문제 풀이

골드4 치고는 쉬운 문제였다고 생각한다.
선이 겹치는 경우와 겹치지 않는 경우로 나눠서 생각하면 된다.
선이 겹치는 경우(앞 선의 끝 점이 뒷 선의 시작점과 끝 점 사이에 있는 경우)에는 선을 계속해서 연장하다가, 겹치지 않는 경우가 나오면 그때 길이를 더해주고 다시 새로운 길이를 구하기 시작한다.

import sys

input = sys.stdin.readline
n = int(input())

line = []
h = []
for _ in range(n):
    a, b = map(int, input().split())
    line.append((a, b))
line.sort()

start = line[0][0]
end = line[0][1]
result = 0

for i in range(1, n):
    # 겹치는 경우
    if line[i][0] <= end < line[i][1]:
        end = max(end, line[i][1])

    # 겹치지 않는 경우
    elif line[i][0] > end:
        result += end - start
        start = line[i][0]
        end = line[i][1]

result += end - start
print(result)