malloc3141592   1년 전

같은 코드를 python3으로 제출했을 때는 시간초과가 떴었는데, pypy3으로 제출하니 정답처리되었습니다

일반적으로 pypy3이 python3보다 빠른 건 알고 있는데, 혹시 이 코드에서 어떤 걸 고치면 python3에서도 시간초과가 안뜰까요?

kevin1211   1년 전

2 99999999

이 예제를 입력해보시면 시간이 꽤 오래 걸린다는 것을 알 수 있습니다. 실제 모르는 예제는 이것보다 더할 것이구요

시간이 오래 걸리는 원인은 쓸데없는 부분을 전부 탐색한다는 것입니다.

for문을 통해 반복을 하였는데 위 예제같은경우 총 2500만번의 반복을 돌게 되고, 이는 간단한 코드라도 파이썬에서는 시간초과의 위험이 있습니다.

사실 합이 최소가 되기 위해서는 결과값이 둘다 처음 입력받은 값의 곱의 제곱근에 가까울수록 합이 작기 때문에

sqrt(dv) 이상의 수를 확인하는건 사실상 무의미합니다.

그 이후는 이미 앞에서 탐색했거나 답이 무조건적으로 아닌 수들밖에 없기 때문이죠

그래서 for문 안의 dv//2+1을 int(dv**0.5)+1같이 바꾸어 준다면 시간초과가 나지 않을 것입니다.

wider93   1년 전

위 2 99999999는 문제의 조건을 만족하지 않습니다

kevin1211   1년 전

앗 수정하겠습니다

2 99999998

이걸로 하면 되겠네요

malloc3141592   1년 전

덕분에 해결했습니다. 감사합니다

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