[BOJ] 백준 2565 전깃줄 (Swift)

문제

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

2565번: 전깃줄

풀이

전깃줄이 교체하는지 어떻게 알 수 있을까요?
(1, 5), (2, 4)를 보시면 교차하고 있는 형태입니다.

(1, 3), (2, 4)은 어떨까요?
두 전깃줄이 교차하고 있지 않습니다.
(a1, b1), (a2, b2) 일 때,

a1 < a2 && b1 > b2 인 경우 교차한다고 할 수 있습니다.

연결되어 있는 위치를 입력받은 후,
a를 기준으로 오름차순으로 정렬해준다면 b만 확인해도 교차하는지 하지 않는지 알 수 있겠네요.

예제입력을 한 번 정렬해봅시다.
(1, 8), (2, 2), (3, 9), (4, 1), (6, 4), (7, 6), (9, 7), (10, 10)
이 되겟네요.

b만 보면
8, 2, 9, 1, 4, 6, 7, 10 입니다.

8의 입장에서 보았을 때, 오른쪽 인덱스로 가면서 8보다 더 작다면 나와 교차하는 선분의 갯수일 것입니다.
그렇다면 8보다 더 큰 것은 교차하지 않는 것이겠죠??

어라.. 그렇다면 증가하는 부분 수열을 구하면, 교차하지 않는 전봇대를 새로 깔 수 있는 것과 동일하지 않을까요?
증가하는 가장 긴 부분 수열은 {1, 4, 6, 7, 10} 이므로 전깃줄이 교차하지 않고, 5개를 최대로 깔 수 있겠네요.

즉, 8, 2, 9를 삭제한다면 모든 전깃줄이 교차하지 않게 만들 수 있습니다.

소스코드

후기

문제를 어떤식으로 풀어야할 지도 모르겠었다..
맨 처음 완전탐색을 떠올렸는데, 말도 안되는 생각이였습니다.

LIS를 응용해서 이런식으로 풀 수 있다니 신기하고 재밌었던 문제였습니다.