msw0909   2년 전

1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000

이므로 N은 1024, M은 100,000일 때 최대가 되어서.  시간 복잡도가  O(NxM)이면 시간초과가 떠야 하는데, 아래의 코드는 정상적으로 돌아가는 것으로 보입니다.  n이 1024, m=100000에 해당하는 케이스를 넣어주세요.

djm03178   2년 전

현재 데이터에서의 최악의 케이스가 어떤지 확인해보지는 않았지만, 1억 정도가 통과하는 건 전혀 무리가 아닌 것 같습니다. 요즘 컴퓨터는 1초에 10억도 돌리니까요. PyPy3의 속도를 감안하더라도 각 연산이 충분히 가볍기 때문에 보너스 시간만으로 충분히 가능해 보입니다.

msw0909   2년 전

흠 제가 알기로는 시간제한이 1초일 때는 체점용 서버에서는 천만~2천만 연산 정도로 잡는다고 알고 있었는데, 잘못 알고 있었나보네요. 답변 감사합니다.  

djm03178   2년 전

간단히 테스트해본 결과 x2-x1+1의 합이 1억이 넘는 케이스는 존재하는 것으로 확인됩니다. C++ 기준으로는 332ms에 통과하네요.

연산 수와 시간의 관계에 대한 것은 https://djm03178.tistory.com/2... 를 읽어보시면 좋을 것 같습니다.

msw0909   2년 전

오오오오 자세한 답변 감사합니다:)

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