Algorithm/Acmicpc
1365 꼬인 전깃줄 [JAVA]
문제분석https://www.acmicpc.net/problem/1365 X -> Y로 하나의 전선씩 연결되어 있는데, 이 중 최소의 전선을 잘라 전선끼리 겹치는 것이 없게 만드는 것이 목적이다. 전선이 서로 겹치지 않기 위해선 최종적으로 남는 각 전선 쌍들이 단조적이여야 한다.즉, 1-2 / 2-3/ 3-4 이런식으로 서로 겹치지 않아야 한다. 이런 순차적인 쌍들의 최댓값을 찾는 것이 최소의 전선을 자르는 방법이기에 이 문제는 LIS(최장 증가 부분수열) 알고리즘으로 접근할 수 있다. N = 10^5 이기에 O(N^2)으론 시간을 맞출 수 없다. https://velog.io/@min-ji99/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B0%80%EC%9E%A5-%EA%B..
