boj_2565_전깃줄

https://www.acmicpc.net/problem/2565 <풀이> 좌측 그림은 input으로 주어진 것을 그림으로 나타낸 것이고, 우측 그림은 이 테스트케이스가 정답이 될 때를 그림으로 나타낸 것이다. 그렇다면, 모든 전깃줄이 서로 겹치지 않기위한 조건을 한 번 생각해보자.

전깃줄이 겹치지 않으려면, "나보다 위에있는 전깃줄들은 나보다 아래로 내려오면 안된다." 는 조건이 필요하다. 우측 그림을 보면 A입장에서 더 낮은 위치의 전깃줄들은 B에도 항상 더 낮은 위치에 연결되어 있다. 8 2 9 1 4 6 7 10 이 말을 바꿔생각하면, 서로 겹치지않는 전깃줄의 개수는 "증가하는 부분 수열의 최대 길이" 이다.

따라서, 이문제를 풀기위..........