12015번 - 가장 긴 증가하는 부분 수열 2
for문을 아무리 아무리 줄여봐도
LIS 구하기 위해서 이중 for문은 돌아야하니까 시간초과가 뜨는데
어떻게 시간을 줄일수 있는 방법이 있나요?
별다른 제약사항이 있는거 같지도 않은데
이중 for문을 돌 때 두 번째 for문은
A[0] ~ A[i-1] 중 A[i]보다 작으면서 가장 긴 증가수열을 만들 수 있는 수를 찾으셨을 겁니다. (코드가 없어서 잘 모르겠네요..)
안쪽 for문을 Segment tree나 이진탐색을 이용해서 O(N)이 아닌 O(log N)으로 줄일 수 있는 방법이 있습니다.
자세한 방법은 검색을 해보심이... 제가 설명을 잘 못해서ㅠㅠ 죄송합니다..
댓글을 작성하려면 로그인해야 합니다.
sa2166 7년 전
for문을 아무리 아무리 줄여봐도
LIS 구하기 위해서 이중 for문은 돌아야하니까 시간초과가 뜨는데
어떻게 시간을 줄일수 있는 방법이 있나요?
별다른 제약사항이 있는거 같지도 않은데