dkgfued   11달 전

O(n) 밖에 안되는데.. 시간초과가 자꾸 나네요..

우선 이분법으로 개수 맞는거 찾고

그뒤에 최대값 찾게끔 알고리즘을 작성했는데 더이상 방법이 생각나질 않습니다.. 도와주세요!

yukariko   11달 전

이분법의 코드를 살펴보면 항상 정확한 값이 나타나는 경우에만 종료되게 됩니다.

하지만 입력에따라 딱 떨어지는 값이 나오지 않을 수 있습니다.

아마 그로인한 무한루프가 시간초과의 원인이지 않을까 생각됩니다.

dkgfued   11달 전

정말 어렵네요 괜히 정답률 20%이하인게 아니였네... 포기해야겠어요..

yukariko   11달 전

거의 다 오셨다고 생각합니다.

저 또한 이분법만 사용하여 해결했습니다.

이분법의 종류는 binary search 말고도 lower bound나 upper bound가 있는데 이것을한번 찾아보세요.

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