[algorithm] 백준 2170 - 선 긋기

[algorithm] 백준 2170 - 선 긋기

 

안녕하세요. 심심한 코딩쟁이입니다.

 

오늘은 백준 2170번 문제 - 선 긋기 의 풀이를 살펴보도록 하겠습니다.

 

풀이에 사용한 언어는 Python3 입니다.

 

문제 해석과 풀이 다 함께 살펴보시죠.

 

알고리즘

---

백준 BAEKJOON 2170

 

백준 2170번 선 긋기 문제 보러가기

 

반응형

 

문제 해석

 

문제에 나온 상황을 보면 자를 대고 선을 여러 번 긋는데 그어진 줄의 총 길이를 출력하는 문제이다.

입력값으로는 몇 번 줄을 긋는지와 줄을 그을 때 시작점과 끝점의 위치가 주어진다.

겹치는 부분을 잘 제거하면서 차근차근 문제를 풀어봅시다.

 

풀이

 

# 2170 선 긋기
import sys

N = int(sys.stdin.readline())

points = list(tuple(map(int, sys.stdin.readline().split())) for _ in range(N))
points.sort()

start, end = points[0]

length = 0

for i in range(1, N):
    new_start, new_end = points[i]
    
    if end > new_start:
        end = max(end, new_end)
    else:
        length += (end - start)
        start, end = new_start, new_end
length += (end - start)

print(length)

 

풀이 해석 및 팁

 

풀이를 살펴보면 사실 크게 어려운 부분은 존재하지 않습니다.

하지만 중간에 tuple을 이용해 입력값을 받아오는 부분이 존재합니다.

이는 메모리 초과를 피하기 위함입니다. 튜플을 사용하면 메모리를 더 적게 사용하고 시간 또한 단축됩니다.

for 반복문 안에서는 선을 긋는 점들을 하나씩 불러와서 겹치는 부분이 있을 땐 끝점을 갱신해 주고

겹치는 부분이 없을 경우 length에 길이를 갱신하고 다시 시작점과 끝점을 바꿔주는 방식으로 반복이 진행됩니다.

반복문이 모두 끝나면 최종적으로 선의 길이를 갱신한 후 출력을 해주면 문제가 해결됩니다.

---

여기까지 백준 2170번 선 긋기 문제 풀이였습니다.

이번 문제의 정답률은 35% 정도입니다.

 

아마도 메모리 초과 또는 시간 초과로 인해 정답률이 낮아진 것으로 보입니다.

 

궁금하신 점은 댓글로 남겨주시기 바랍니다.

 

감사합니다.