2 99999999
이 예제를 입력해보시면 시간이 꽤 오래 걸린다는 것을 알 수 있습니다. 실제 모르는 예제는 이것보다 더할 것이구요
시간이 오래 걸리는 원인은 쓸데없는 부분을 전부 탐색한다는 것입니다.
for문을 통해 반복을 하였는데 위 예제같은경우 총 2500만번의 반복을 돌게 되고, 이는 간단한 코드라도 파이썬에서는 시간초과의 위험이 있습니다.
사실 합이 최소가 되기 위해서는 결과값이 둘다 처음 입력받은 값의 곱의 제곱근에 가까울수록 합이 작기 때문에
sqrt(dv) 이상의 수를 확인하는건 사실상 무의미합니다.
그 이후는 이미 앞에서 탐색했거나 답이 무조건적으로 아닌 수들밖에 없기 때문이죠
그래서 for문 안의 dv//2+1을 int(dv**0.5)+1같이 바꾸어 준다면 시간초과가 나지 않을 것입니다.
malloc3141592 1년 전 1
같은 코드를 python3으로 제출했을 때는 시간초과가 떴었는데, pypy3으로 제출하니 정답처리되었습니다
일반적으로 pypy3이 python3보다 빠른 건 알고 있는데, 혹시 이 코드에서 어떤 걸 고치면 python3에서도 시간초과가 안뜰까요?