글 읽기 - 이 코드는 왜 시간초과가 안뜰까요 ?

ckddn1224 3년 전 1

질문 게시판에 있는 다른 질문글을 보고 궁금해서 질문남깁니당

n이 40이고 주어진 수열이 모두 0이라고 하면

8백만 * 40번 = 3억2천번 의 대입연산이 일어날텐데 이정도 연산은 1초 시간제한 안에 들어오나요 ??

long k[8000001];
main(n,s,i,j,a)
{
    scanf("%d%d",&n,&s);
    for(i=0;i<n;i++)
        {
            scanf("%d",&a);
            if(a<0)
                for(j=-a;j<=8000000;j++)k[a+j]+=k[j];
            else 
                for(j=8000000-a;j>=0;j--)k[a+j]+=k[j];
            k[a+4000000]++;
        }
    printf("%lld\n",k[s+4000000]);
}

djm03178 3년 전 5

3억번 정도는 연산 하나 하나가 가볍다면 여유 있게 1초 내에 실행될 수 있습니다. 이 코드 정도의 연산이라면 10억번도 거뜬할 것 같습니다.

ckddn1224 3년 전 0

아하 그렇군요.. 감사합니다!

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

문제

문제

출처

ICPC

이 코드는 왜 시간초과가 안뜰까요 ?

ckddn1224 3년 전 1

djm03178 3년 전 5

ckddn1224 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말