태그:
전봇대에 걸려있는 전깃줄 중 일부를 제거하여 겹치는 줄이 없게 만들 때 최소로 제거하는 전깃줄의 개수를 구하는 문제입니다. 이 문제는 정렬과 LIS를 이용하여 풀 수 있는데, 우선 받아들인 좌표를 한 쪽 전봇대에 대해 정렬합니다. 정렬된 좌표 중 다른 쪽 전봇대에 해당하는 좌표들을 순서대로 배열에 저장합니다. 이 배열의 LIS를 구하면 겹치지 않고 존재할 수 있는 최대의 전깃줄 개수가 됩니다. 따라서 전깃줄 개수에서 LIS의 길이를 빼면 최소로 제거하는 전깃줄의 개수가 됩니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-04-01 00:35:01 |