[BOJ] 백준 2170 선 긋기

문제 링크

15922 아우으 우아으이야!! 문제와 같은 문제입니다. 예전에 썼던 풀이 그대로 퍼올게여.

문제를 풀기 위해 수직선들을 좌표가 낮은 순으로 정렬하자. 그리고 앞의 수직선부터 탐색한다.

인접한 두 수직선의 관계는 다음과 같다.

빨간 선의 양 끝점을 $s, e$라 하고, 파란 선의 양 끝점을 $ns, ne$라 하자.

①은 $s \leq ns$ & $ne \leq e$인 경우이고, 더 작은 선분을 무시하는걸로 해결할 수 있다.

②는 $ns < e$인 경우이고, 중복해서 더해지는 $e - ns$값을 빼주면 된다.

③의 경우엔 그냥 둘 다 더하면 된다.

파란 선은 현재 내가 보고있는 선분, 빨간 선이 파란 선분의 바로 직전 선분이다.

정답 코드