13909번 - 창문 닫기
정답이긴 한데 이런식으로 풀어보라고 낸 문제는 아닌 거 같네요
어떤 창문 X가 열려있으려면 X의 약수가 홀수개여야 합니다.
즉, X는 어떤 수의 제곱수여야 합니다.
1이상 N이하의 수 중에서 제곱수는 당연히 sqrt(N)개 존재합니다.
그럼 저 정답이 제출자가 의도한 정답인거에요?
단순하게 풀기에는 N이 너무 크므로 이론상 O(log(N)) 보다 빨리 풀어야 합니다.
생각할 수 있는 가장 쉬운 것은 제곱근을 O(log(N))에 계산하는 것이므로 의도한 풀이가 맞습니다.
제곱근 함수가 없는 경우에 그것을 직접 구현한다고 생각한다면 쉬운 풀이는 아니라는 것을 알 수 있을 것입니다. (사실 쉽습니다만)
----
정정 >> O(sqrt(N))에 풀면 됩니다 O(log(N))은 너무 빠르네요.
감사합니다
댓글을 작성하려면 로그인해야 합니다.
system_sadly 2년 전
정답이긴 한데 이런식으로 풀어보라고 낸 문제는 아닌 거 같네요