sa2166   7년 전

for문을 아무리 아무리 줄여봐도

LIS 구하기 위해서 이중 for문은 돌아야하니까 시간초과가 뜨는데


어떻게 시간을 줄일수 있는 방법이 있나요?

별다른 제약사항이 있는거 같지도 않은데

jjwdi0   7년 전

이중 for문을 돌 때 두 번째 for문은

A[0] ~ A[i-1] 중 A[i]보다 작으면서 가장 긴 증가수열을 만들 수 있는 수를 찾으셨을 겁니다. (코드가 없어서 잘 모르겠네요..)

안쪽 for문을 Segment tree나 이진탐색을 이용해서 O(N)이 아닌 O(log N)으로 줄일 수 있는 방법이 있습니다.

자세한 방법은 검색을 해보심이... 제가 설명을 잘 못해서ㅠㅠ 죄송합니다..

댓글을 작성하려면 로그인해야 합니다.