minjun623   6년 전

문제 시간이 2초가 주어진걸 보면 이분탐색을 이용해서 풀라는 풀이 인줄 알았는데, 루트값을 이용하면 쉽게 풀 수 있을 것 같더라고요.

루트 (n^2+n)이 루트 n보다 크니까 루트 n을 이용해서 해결하는 풀이가 떠올라서 이렇게 풀었는데, 어떤 풀이가 더 효율적인가요?

chogahui05   6년 전

이건 이분 탐색 식도 세우긴 세울 수 있을 거 같아요. greedy하게 세워버리면 되죠..

이것은 O(logn) 정도 복잡도일 거구요.


sqrt 함수는 어떤 식으로 내부에서 구현이 되었는지는 잘 모르겠습니다..만.

바빌로니아 법을 쓰더라도 생각보다 빠르게 근사하는 걸로 알고 있어요. 대충 O(logn) 정도..

앞에 붙는 상수 차이만 있는데요. 어짜피 logn이 상당히 작은 지라.. 테케가 상당히 많이 주어지지 않는 이상

그렇게 의미있는 차이가 발생할 거 같진 않네요.


비교해 보고 싶으시다면

TC를 100만 ~ 1000만개 정도 준 다음에 비교해 보는 방법이 제일 좋을 거 같네요.

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