2247번 - 실질적 약수
시간 제한이 2초이며, n 제한이 2억인 것은 O(n) 시간복잡도를 가지는 풀이가 통과하는 가에 대한 애매한 요소가 다소 있어보입니다.
정확한 출제 의도는 모르겠지만 O(n*sqrt(n))의 풀이가 통과되는 것을 방지하려 하신 것 같습니다.
이를 명확히 하기 위해, 출제 의도가 O(n)이라면, 10^7과 같이 n 제한을 약간 줄이고, O(sqrt(n))을 의도하셨다면, n의 범위를 10^9와 같이 늘리는 것이 좋아보입니다.
댓글을 작성하려면 로그인해야 합니다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
한국어 | English (Beta)
AltStyle によって変換されたページ (->オリジナル) / アドレス: モード: デフォルト 音声ブラウザ ルビ付き 配色反転 文字拡大 モバイル
ian0704 1년 전 1
시간 제한이 2초이며, n 제한이 2억인 것은 O(n) 시간복잡도를 가지는 풀이가 통과하는 가에 대한 애매한 요소가 다소 있어보입니다.
정확한 출제 의도는 모르겠지만 O(n*sqrt(n))의 풀이가 통과되는 것을 방지하려 하신 것 같습니다.
이를 명확히 하기 위해, 출제 의도가 O(n)이라면, 10^7과 같이 n 제한을 약간 줄이고, O(sqrt(n))을 의도하셨다면, n의 범위를 10^9와 같이 늘리는 것이 좋아보입니다.