[python/백준] 2170번: 선 긋기

 

https://www.acmicpc.net/problem/2170

2170번: 선 긋기

 

 

 

⭐ 문제

 

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

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

 

 

 

⭐ 코드 분석

 

각 선이 끝나는 점만 비교해 주면 된다

 

1) X가 B보다 크거나 같은 경우

- 이는 먼저 오는 선이 두 번째 선을 완전히 포함하고 있는 경우라고 할 수 있다.

Ex) (1, 10), (2, 5) or (1, 10), (2, 10)

 

이 경우, 두 번째 선은 고려할 필요 없이 그냥 1 ~ 10까지의 거리를 구해주면 두 선의 길이를 알 수 있다.

 

2) A <= X < B인 경우

- X가 A와 B 사이에 위치한 경우, 두 선은 겹쳐있는 것으로 생각할 수 있다. 따라서, 두 선의 총 길이는 첫 번째 선이 시작하는 곳에서 두 번째 선이 끝나는 곳까지의 거리가 된다.

 

Ex) (1, 5), (2, 7) -> 1 ~ 7까지의 거리

 

3) X가 A보다 작은 경우

- 두 선이 전혀 겹치지 않은 것으로 간주할 수 있다. 따라서, 두 선의 길이를 각각 구해준 후 더해주면 선들의 길이의 합이 된다.

Ex) (1, 2), (3, 4) -> 총 길이는 2

 

반복문을 돌면서 합칠 수 있는 선들은 합쳐주고, 합칠 수 없다면 지금까지 합쳐진 선의 길이를 ans에 더해주고, 그 다음 선의 시작점과 끝점을 각각 왼쪽, 오른쪽 포인터로 갱신해 작업을 반복해주면 된다.

 

 

 

⭐ 코드

import sys

input = sys.stdin.readline

n = int(input())
lines = []

for _ in range(n):
    lines.append(tuple(map(int, input().split())))

lines.sort()

left = lines[0][0]
right = lines[0][1]
ans = 0

for i in range(1, n):
    if right >= lines[i][1]:
        continue

    elif lines[i][0] <= right < lines[i][1]:
        right = lines[i][1]

    elif right < lines[i][0]:
        ans += right - left
        left = lines[i][0]
        right = lines[i][1]

ans += right - left
print(ans)