yjkim9591   1년 전

혹시 몰라서 1000000 limit도 걸어놨는데 왜 시간 초과가 뜨는지 모르겠습니다. 소수 구하는 방법도 제대로 한 것 같고, 판정 방법도 그리 루프를 많이 돌릴 것 같지는 않는데 시간초과가 뜹니다ㅠㅠ

pielo   1년 전

1. 문제에서 테스트 케이스 개수는 100,000개 이하라고 제시되었으므로 21번째 줄 count>1000000 조건문은 필요하지 않습니다.

2. 현재 코드는 22번째 줄에서 28번째 줄까지 각 테스트 케이스(n)를 입력받을 때마다 에라토스테네스 체 방법을 통해 새롭게 소수 확인 배열(arr)을 만들고 있습니다. 이렇게 되면 이전에 만들었던 소수 배열에 대한 정보가 사라지게되므로 불필요한 작업을 중복해서 하게 됩니다.

해당 코드를 19번째 줄 while문 밖으로 빼고 가능한 입력 범위 내의 모든 소수 배열을 한번만 생성하세요.

3. 해당 배열(arr)의 자료형을 다시 확인하세요.

4. OdivP() 함수의 알고리즘 시간 복잡도를 더 줄일 수 있습니다. (Hint: 만약 i가 소수라면, n - i가 소수인지 확인합니다.)

5. 출력 형식을 다시 확인하세요. 공백에 주의하세요.

6. 도움이 필요한 당신에게 <- 해당 글 참고하셔서 앞으로 질문 글 올리실 때, 코드 인덴트 맞추시고 함수 알고리즘 원리를 추가해주세요.

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