namoo991026   1년 전

코드 두개를 보시면 

a=a//k
b=b//k 

(16~17번째줄)

부분이랑 

a=a//min_num
b=b//min_num

(46~47번째 줄)

이렇게만 차이나고 똑같은 코드입니다

math.gcd를 안쓰고 이렇게 하면 시간복잡도가 45,000,000도 갈 수 있음을 깨닫고 

다른 방법으로 해봐야지 하다가 그냥 이거만 고쳐봤는데 아래 코드는 통과하고 위 코드는 시간초과 했습니다


아무리 생각해도 두 코드의 차이를 모르겠습니다

왜 차이가 나는걸까요??

wizardrabbit   1년 전

안녕하세요, 예상하셨겠지만 두 코드의 기능상 큰 차이는 없습니다.

다만 두 코드 모두 문제의 시간제한의 커트라인에 아슬아슬하게 걸칠 정도의 수행시간이 나와 그 작은 수행시간의 차가 채점 결과를 결정지었습니다. 코드의 수행시간은 본래 일정하지 않은 것도 있고요. 통과한 코드의 수행시간이 4900ms대인데, 본 문제의 제한시간은 Python에 주어지는 시간 보너스를 감안했을 때 5000ms입니다.

몇몇 예외는 있습니다만 대부분의 상황에서는 PyPy3으로 제출했을 때 훨씬 빠른 수행시간으로 코드가 실행되도록 할 수 있습니다. Python 3과 PyPy3은 언어 명세는 같으면서 구현체만 다르기 때문에 Python 3의 코드를 그대로 PyPy3으로 제출하실 수 있습니다. Python의 느린 속도로 인해 학습에 지장이 있으시다면 PyPy3을 적극 활용해 보세요. 이 상황에서 질문자님의 코드는 600ms ~ 800ms 정도가 나왔습니다.

oh040411   1년 전

백준 채점환경이 제출할 때마다 조금씩 달라서 실행 시간에 10% 정도의 오차가 발생할 수 있습니다. 통과한 코드가 4900 ms 정도 (파이썬 제한은 5000ms)에 동작하는데, 이 정도면 똑같은 코드를 여러 번 내도 시간 초과가 날 수도 있고 통과할 수도 있습니다.

namoo991026   1년 전

아하... 통과했던건 그냥 운이 좋았던 거군요
gcd를 쓰도록 해야겠습니다 ㅎㅎ

답변주신 분들 다들 감사드립니다!

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