전깃줄 문제는 정말 어려웠다.
결국 힌트를 얻기위해 돌아다니다가 LIS로 푸는 문제라는 것을 알았다.
근데 LIS가 잘 구현이 안되어서 찾아보며 풀었다.
LIS는 배열에서 최장 증가하는 부분 수열을 찾는 것이다.
이 것을 찾는 이유는 문제를 계속 들여다보면 x값(왼쪽)을 정렬시킨 상태에서 y값들(오른쪽)이 계속적으로 증가되어야
서로 교차되지 않는 최대의 개수를 찾을 수 있게 된다.
우선 LIS알고리즘에 대해서 정확히 다시 숙지 할 필요가 있고, 또한
LIS알고리즘은 구하는 즉시 정렬되어 있는 줄 알았는데 그게 아니라
가장 최대값을 구하기 위해서는 한 번 또 정렬을 해줘야 한다는 것을 알았다.
그래서 구조체 형식으로 왼쪽 값 오른쪽 값에 대한 값들을 받아와서
왼쪽 값을 기준으로 정렬한 후에 오른쪽 값을 기준으로 LIS 최장 증가 부분수열의 개수를 찾은 다음에
N에서 빼주면 답이 나온다.
