글 읽기 - 4948번 시간초과 질문

lhj8231 2년 전 0

혹시 이렇게 작성할 경우 시간초과가 되는 이유를 알 수 있을까요? 제가 짠 코드도 시간복잡도O(n^3)이고,

다른 분들 정답 예시도 시간복잡도 O(n^3)이라고 생각하는데 이유를 모르겠습니다.

//제가 짠 코드
#include <iostream>
#include <cmath>
#include <string>  
#include<algorithm>
#include<vector>



using namespace std;

bool Pnum(int a) {
    if (a < 2)
        return false;
    else {
        for (auto i = 2; i < a; i++) {
            if (!(a % i))
                return false;
        }
        return true;
    }
}

void Brgj(void) {
    vector<int>vec;
    int index = 0;
    while (1) {
        try {
            int n;
            cin >> n;
            if (n == 0)
                throw n;
            vec.emplace_back(0);

            for (auto i = n + 1; i <= 2 * n; i++) {
                if (Pnum(i))
                    vec[index] += 1;
            }
            index++;
        }
        catch (int exp) {
            for (auto i = 0; i < vec.size() - 1; i++)
                cout << vec[i] << '\n';
            return;
        }

    }
    
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    Brgj();

    return 0;
}

bamgoesn 2년 전 0

우선 42행에서 for문 종료의 조건문이 잘못 작성되어 마지막 답안은 출력되지 않음을 말씀드립니다.

또한 위 코드의 시간복잡도는 각 테스트케이스별로 O(n^2)입니다. Pnum(n)의 시간복잡도가 O(n)이고, 이를 35행에서 O(n)회 반복하기 때문입니다.

이 문제에서 n의 제한은 100000 정도로, 테스트케이스가 여러개 있는 문제의 경우 시간 초과를 받게 됩니다. 10^10회의 루프는 정말 단순한 연산의 반복이 아닌 이상 통과하기 어렵거든요.

이 문제를 푸는 대부분의 정답 코드는 아무리 못 해도 "각" 테스트케이스를 처리하는 시간복잡도가 O(n loglogn) 정도입니다. 잘 하면 "전체" 테스트케이스를 처리하는 시간복잡도가 m=123456에 대해 O(m loglogm) 또는 O(m)이 나오게 할 수 있습니다.

어느쪽이든 O(n^2)으론 무리입니다. O(n^3)이라면 더욱 어렵고요.

adfsfsf 2년 전 0

이미 푸셨는지는 모르겠지만 적어보자면, 앞의 테스트케이스에서 구한 소수들의 정보를, 뒤의 테스트케이스들에서 다시 구해야 할까요? 재활용할 방법이 있지 않나요? 한 번 그 방법을 생각해보세요.

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

문제

문제

출처

ICPC

4948번 시간초과 질문

lhj8231 2년 전 0

bamgoesn 2년 전 0

adfsfsf 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말