글 읽기 - 시간 초과가 나올리가 없는데 이상하네요..ㅠ.ㅠ

jnk98 8년 전 0

틀렸습니다. 라면 몰라도, 가장 시간이 많이 걸리는 1000,001을 대입해도 즉시 답이 나오는데, 시간 초과가 걸리네요..ㅠ.ㅠ

혹시 채점 데이터가 잘못된 건 아닐지...

#include <stdio.h>
#include <stdlib.h>
#define MAX_NUM 250000

int Hprimes[MAX_NUM+1]={0};
char dap[MAX_NUM+1]={0};

// 에라토스테네스의 체와 같은 방식으로 H-prime을 구한다.
// H-primes 만 구하면 나머지는 쉽다.

void make_H_primes()
{
    int i,j,m;

    for(i=1;i<=MAX_NUM;i++) Hprimes[i]=i*4+1;

    for(i=1;i<=MAX_NUM;i++)
    {
        if(Hprimes[i]==0) continue;
        for(j=Hprimes[i];j<=Hprimes[MAX_NUM]/Hprimes[i];j+=4) Hprimes[(j*Hprimes[i]-1)/4]=0;
    }

}

int main()
{
    int i,j,cnt=0;
    int N;

    make_H_primes();

    while(1)
    {

        scanf("%d",&N);
        if(N==0) return 0;
        cnt=0;
        memset(dap,0,MAX_NUM);

        for(i=1;i<=MAX_NUM/5;i++)
        {
            if(Hprimes[i]==0) continue;
            if(Hprimes[i]>N) break;

            for(j=i;j<=MAX_NUM/5;j++)
            {
                if(Hprimes[j]==0) continue;
                if((long long) Hprimes[i]*Hprimes[j]>(long long)N) break; // int를 넘어갈 수 있음.. 주의 !!!
                else
                {
                    if(dap[(Hprimes[i]*Hprimes[j]-1)/4]==0)  // 쉽다고 생각했으나 ...중복되는거 체크해서 제거해 주어야 제대로된 답이 나옴 ㅠ.ㅠ
                    {
                        cnt++;
                        dap[(Hprimes[i]*Hprimes[j]-1)/4]=1;
                    }
      //              printf("%d %d %d\n",Hprimes[i],Hprimes[j],Hprimes[i]*Hprimes[j]);
                }
            }
        }

        printf("%d %d\n",N,cnt);
    }
    return 0;
}

yukariko 8년 전 0

단순히 반복만 따져보면

50000^2 가량 되는거같은데

Break를 고려해서 10000^2 라고해도

1초면 시간초과가 날 수있지않을까요?

jnk98 8년 전 0

댓글보고 혹시나 해서 측정해 보았는데,

시간이 가장 많이 걸리는 1000001 입력시 0.01초 나오네요..

아무래도 체점에 문제가 있는 듯..

yukariko 8년 전 0

테스트 케이스가 여러개니까 0.01초 작업이 100개나 1000개필요하면 1초가 넘을것같습니다.

그리고 채점 서버의 사양이 그렇게 좋은편은아니라고 알고있습니다. 따라서 개인컴으로 실험한거보다 좀 더 느릴수도있을거에요.

jnk98 8년 전 1

헉, yukariko 님의 의견이 맞을 것 같군요.

그런데, 그런 경우라면 테스트 케이스의 범위를 명시해야 할 것 같은데 문제가 좀 이상한 듯 ...ㅠ.ㅠ

어쨌건 테스트 아주 많을 경우에 빠른 답을 낼 수 있도록 뜯어 고쳐봐야 겠네요..

의견 감사합니다. ^^

jnk98 8년 전 0

결국 답을 미리 계산해 놓고 출력하는 방식으로 바꾸어서 풀었네요..

(위의 루틴과 유사한데 1회만 전체적으로 돌리고, 답을 미리 저장하는 방식)

그리고, Hprime 구하는 루틴도 잘못되어 있었네요. (위의 방식은 125 같은 값을 Hprime 으로 잘못 잡더군요..ㅠ.ㅠ)

그래서, 위의 루틴과 비슷하게 바꾸었더니 맞았네요..^^

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

문제

문제

출처

ICPC

시간 초과가 나올리가 없는데 이상하네요..ㅠ.ㅠ

jnk98 8년 전 0

yukariko 8년 전 0

jnk98 8년 전 0

yukariko 8년 전 0

jnk98 8년 전 1

jnk98 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말