[BOJ] 백준 15922 아우으 우아으이야!!

문제 링크

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

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

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

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

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

②는 $ns < e$인 경우이고, 두 선분의 길이의 합에 중복된 $e - ns$의 값을 빼줌으로써 해결할 수 있다.

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

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

정답 코드

질문, 피드백 환영합니다.