글 읽기 - 이 문제 제한시간이 1초인데 왜 되나요?

mhkim4886 5년 전 0

일단 제가 제출해서 약 32ms로 AC 받은 코드를 첨부합니다.

에라토스테네스의 체를 사용해서 소수를 구해놓은 뒤 소수 리스트를 앞에서부터 보면서 답을 출력하는 방식을 사용했습니다. 대부분 그렇게 짜는 거 같더라구요.

에라토스테네스의 체 부분은 그렇다 치고, 그 아래의 답을 구하는 부분을 보면, 테스트케이스의 수 T와 100만 이하 소수의 갯수 n에 대해 O(Tn)인 것 같습니다. 이때 T <= 100000, n = 약 8만입니다. 그러면 시간 초과가 나는 게 정상인 거 같은데... 왜 안 날까요? 아마 거의 모든 수가 8만보다 훨씬 적은 수의 루프를 돌고 답을 찾을 수 있어서 그런 것 같은데, 이 문제가 항상 1초 안에 작동한다는 것을 증명할 수 있나요?

bool isPrime[1000001];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 3; i <= 1000000; i += 2)
        isPrime[i] = true;
    for (int i = 3; i <= sqrt(1000000); i += 2)
    {
        if (!isPrime[i])
            continue;
        for (int j = i * 3; j <= 1000000; j += i * 2)
            isPrime[j] = false;
    }

    vector<int> primes;
    for (int i = 3; i <= 1000000; i += 2)
        if (isPrime[i])
            primes.push_back(i);

    int n;
    scanf("%d", &n);
    do
    {
        for (int i = 0; i < primes.size(); i++)
        {
            if (isPrime[n - primes[i]])
            {
                printf("%d = %d + %d\n", n, primes[i], n - primes[i]);
                break;
            }
        }
        scanf("%d", &n);
    } while (n != 0);
}

cozyyg 5년 전 4

직접 프로그램을 돌려 보니, 4부터 1000000까지의 짝수 중 답의 작은 소수 쪽이 가장 큰 건 503222일 때 98번째 소수인 523이었습니다. 그러므로 최악의 경우라도 100000*98번의 확인으로 충분하겠네요.

binjinoh 4년 전 0

저도 똑같은 질문이 들었는데

뭐 테스트케이스 때문인것 같네요 ㅎㅎ

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

문제

문제

출처

ICPC

이 문제 제한시간이 1초인데 왜 되나요?

mhkim4886 5년 전 0

cozyyg 5년 전 4

binjinoh 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말