글 읽기 - 시간 초과에 대한 질문입니다.

mij9929 5년 전 0

우선 다른 분들의 질문들을 보고 시간초과 부분이 소수의 가장 작은 차를 구하는 방법을 이중 for문 부분이 시간 초과를 일으킨다고 되어있습니다. 제 에라토스테네스의 체 부분이 맞다고 가정(사실 이것도 에라토스테네스의 체 알고리즘이 맞는지도 모르지만 소수구하기 3단계 4단계를 이걸로 맞았습니다)하면 이중 for문 부분에서 틀렸다는 것이 되겠지요 .하지만 이중 for문 특성상 최대한 돌리는 n의 경우가 n이 10000인 경우일 텐데 제 컴퓨터 기준으로 했을 때 즉각적으로 나오고 있습니다. 그래서 왜 이중 for문이 왜 시간초과가 나오는지 알고 싶습니다.

#include<stdio.h>
int main(){
    int T,arr[10001] = {0,},p=2,k=2,i,n,cnt=0;
    int result1, result2;
    scanf("%d",&T);
    arr[1] = 1;
    
    while( p*p < 10001){ //에라토스테네스의 체
        i=2;
        while(i*p < 10001){
            arr[i*p] = 1;
            i++;
        }
        p++;
    }
  
    for(i=0;i<T;i++){ // 가장 차이가 적은 값을 찾는 코드
        result1 = 0;
        result2 = 0;
        cnt=0;
        scanf("%d",&n);
        for(k=2;k<n;k++){
            for(p=2;p<=k;p++){
                if(arr[k] != 1 && arr[p] != 1 && ((k+p) == n)){
                    if(cnt==0){ // 최초로 찾은 두 소수의 합일 경우
                        result1 = p;
                        result2 = k;
                        cnt++;
                    }
                    else if(result2 - result1 > k-p && cnt!=0) // 차이가 더 작은 소수의 합일 경우
                    {
                        result1 = p;
                        result2 = k;
                    }
                }
            }
            
        }
        printf("%d %d\n",result1,result2);
    }

    
}

mij9929 5년 전 0

문제 자체는 이중 for문을 쓰지않고 풀긴 풀었습니다. 제가 알고 싶은건 왜 이중 for문이 오류가 날 수 밖에 없는지 궁금해서 올렸던 것입니다. 제가 생각해보았을 때는 테스트케이스가 최대이고 n = 10000일 경우 3중 포문으로 O(n^3)이 였을 경우 이긴 한데 맞는지도 궁금합니다.

djm03178 5년 전 0

"테스트케이스가 최대이고"는 정확히 알 수 없습니다. (n은 테스트케이스의 수가 아닙니다.) 테스트케이스의 수의 제한이 명시되지 않은 문제에서는 "출제자의 의도에 맞는 복잡도라면 통과시켜주겠다" 정도로 생각할 수 있는데, n=10000 정도면 n^2은 1억으로 0.1초가 안 걸릴 것이며 사람 눈에는 거의 즉각적으로 나오는 것처럼 보이지만, 이러한 케이스가 100개만 있어도 약 10초에 육박하는 시간이 걸릴 것입니다. 만일 하나의 케이스를 0.0001초에 해결할 수 있다면 100개의 케이스가 있더라도 0.01초면 충분하겠죠.

mij9929 5년 전 0

감사합니다

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

문제

문제

출처

ICPC

시간 초과에 대한 질문입니다.

mij9929 5년 전 0

mij9929 5년 전 0

djm03178 5년 전 0

mij9929 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말