[백준/Python] 2170 선 긋기

문제 링크

2170번: 선 긋기

 

문제 풀이

• 먼저, 입력 받은 리스트를 시작점(x[0])에 대해서 오름차순 정렬하고, 끝점(x[1])에 대해서 오름차순 정렬을 한다.
• 처음의 시작점과 끝점은 각각 리스트의 첫 번째가 되는데, 이 때, 총 길이의 값을 끝점에서 시작점을 뺀 값으로 저장한다.
• 이후 인접한 두 선분은 총 6가지의 케이스가 나오게 되는데, 각 2가지의 케이스씩 묶어서 생각할 수 있다. 첫 번째는 선분 l1의 끝점이 선분 l2의 시작점보다 큰 경우이고, 두 번째는 선분 l1의 끝점보다 선분 l2의 시작점이 같거나 큰 경우이다. 마지막은 선분l1의 끝점이 선분 l2의 끝점보다 큰 경우이다.
• 마지막 케이스는 이미 이전에 선분의 길이를 더해주었기 때문에 따로 더하면 안된다는 점이다.

 

전체 코드

import sys

n = int(sys.stdin.readline())
l = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
l.sort(key=lambda x:(x[0], x[1]))

start = l[0][0]
end = l[0][1]
res = end - start
for i in range(1, n):
    if l[i][0] < end < l[i][1]:
        start = end
        end = l[i][1]
        res += (end - start)
    if start <= l[i][0] and end <= l[i][1]:
        start = end
    if end <= l[i][0]:
        start = l[i][0]
        end = l[i][1]
        res += (end - start)

print(res)