hpns1379   2년 전

주피터에서는 제일 큰 숫자인 1000000를 넣어봐도 바로바로 결과 나오고, 무한 루프도 없는데 시간 초과가 뜨네요...

어디를 더 고쳐야할지 잘 모르겠습니다...ㅠㅠ

bamgoesn   2년 전

1. 테스트 케이스 개수가 100000개까지 될 수 있기에 빠른 입출력이 필요할 수도 있습니다. 다만 이게 시간 초과의 주 원인은 아닌 것 같습니다.

2. sosu는 m이 소수인지 판별할 때 2부터 m까지 모든 수를 나눠보지만, 사실은 루트m까지만 나눠봐도 충분합니다. 그 수까지 나눠봤을 때 하나도 나눠지지 않았는데, 그보다 큰 수가 m을 나눈다면, 나눠서 나온 수는 루트m보다 작고 진작 m을 나눌 수 있었어야 하기 때문입니다.

3. 여러 테스트 케이스를 다룰 때, 특정 수가 소수인지 아닌지를 sosu를 통해 그때그때 다시 확인합니다. 이 과정에서도 시간 손실이 있습니다. 예를 들어 입력으로 30, 40이 들어왔을 때, 30에 대한 답을 계산하는 동안 3, 5 등이 소수인지 아닌지 이미 판단했을 텐데 40에서 같은 일을 또 합니다. 안 그래도 sosu를 실행하는 데에 시간이 오래 걸리는데 여기서 시간이 더 오래 걸리게 됩니다.

4. 1000000은 숫자는 크지만 그렇게 시간이 오래 걸리는 테스트 케이스가 아닙니다. 1000000 = 17 + 999983 으로 17은 상당히 작은 수이기 때문입니다.

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