[백준-파이썬] 2170 : 선 긋기

문제 보러가기

접근 🍁

쭉~ 입력을 받은 후에 정렬을 했다. 정렬을 하는 게 매우 중요하다..!!

start와 end는, 다른 선들과 겹치지 않는 선은 계산을 끝내고, (다른 선들과 겹칠 가능성을 가진) 당시에 가장 긴 선을 의미한다.

맨 처음 시작점, 도착점을 각각 start, end에 대입했다. 그 다음부터 각각의 시작점, 도착점과 start, end를 비교해 보면 아래 그림의 세 가지 경우 중 하나가 된다. (정렬을 했으니까 항상 그 시점의 시작점보다 start가 작거나 같을 것이다. 그래서 아래 세 가지 경우만 있다.)

1) 두 선이 겹치고, 그 때 꺼낸 도착점이 end보다 뒤에 있는 경우.
그러면 start는 그대로 두고, end는 그때 꺼낸 도착점으로 업데이트한다.

2) 두 선이 겹치고, 그 때 꺼낸 도착점이 end보다 앞에 있는 경우.
start, end 둘 다 그대로 둔다.

3) 두 선이 겹치지 않는 경우.
이제 start, end와 겹치는 선은 없으므로, 그 길이를 ans에 더한다. 그리고 그때 꺼낸 시작점과 도착점으로 start, end를 업데이트한다.

코드 👩‍💻

import sys

input = sys.stdin.readline

N = int(input())
origin_lines = list(tuple(map(int, input().split())) for _ in range(N))

origin_lines.sort()  # 정렬

# 맨 처음 꺼 기준으로
start = origin_lines[0][0]
end = origin_lines[0][1]

ans = 0
for k in range(1, N):  # 나머지 선들 보자
    now_start, now_end = origin_lines[k]

    # 겹치는 경우 => 시작점은 무조건 원래 있던 게 더 앞섬. 도착점은 비교해서 정하기.
    if end > now_start:
        end = max(end, now_end)

    # 안 겹치는 경우
    else:
        # 기존 것을 ans에 더하기
        ans += (end - start)
        # 새로운 걸로 업데이트
        start, end = now_start, now_end

ans += (end - start)
print(ans)