[BOJ] 2170

less than 1 minute read

선 긋기

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

모든 선들을 pair로 저장해두고 오름차순으로 sort합니다.
뒤에 나오는 선이 이미 그어져 있는 영역과 겹친다면 그어져 있는 영역의 오른쪽 좌표를 갱신합니다.
겹치지 않는다면 여태 그어져 있는 영역의 길이를 더해주고 새로 나온 선으로 영역의 왼쪽, 오른쪽 좌표를 갱신합니다.
(오름차순으로 정렬했기 때문에 이렇게 해도 문제가 되지 않습니다.)

정답 코드 https://github.com/Geniemo/BOJ/blob/master/2170.cpp

Categories:

Updated:

Leave a comment