글 읽기 - c++ 시간초과..?

tpfpske 2년 전 0

주어진 수들을 정렬 후 인접한 항의 차들의 최대공약수를 구하고 그 약수를 출력했습니다.

75%~83%에서 느려지더니 시간초과가 나네요.

의심되는 곳은 34-40줄의 약수를 출력하는 for문인데.. 이것을 더 줄일 수 있는 방법이 있을까요?

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int N; // 2 <= N <= 100
int S[100];
vector<int> D;

int gcd(int a, int b) { return a % b ? gcd(b, a % b) : b; }

int main()
{
    scanf("%d", &N);

    for (int i = 0; i < N; ++i)
    {
        scanf("%d", &S[i]);
    }

    sort(S, S + N);

    for (int i = 1; i < N; ++i)
    {
        D.push_back(S[i] - S[i - 1]);
    }

    int M = S[1] - S[0];
    for (int m : D)
    {
        M = gcd(M, m);
    }

    for (int i = 2; i <= M; ++i)
    {
        if (M % i == 0)
        {
            printf("%d ", i);
        }
    }

    return 0;
}

djs100201 2년 전 2

약수의 출력은 sqrt(n)까지만 검사하면 됩니다

znyuk96 2년 전 3

최악의 경우

ex)

999999998

ex)

333333332

666666665

999999998

등의 경우에 시간 초과에 걸릴 수 있습니다.

sqrt(M)까지만 약수를 확인하시고, 나눠지는 경우 n/i (나눠진 숫자와 곱해져 n 을 이루는 pair)를 저장했다가 후에 줄력하는 방식으로 구현하면 됩니다.

참고로 sort가 시간 초과의 문제는 아니나, sort 필요 없이 abs(s[n-1] - s[n]) 으로 gcd에 입력을 주면 되는 것도 참고하시면 좋을 것 같습니다.

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

문제

문제

출처

ICPC

c++ 시간초과..?

tpfpske 2년 전 0

djs100201 2년 전 2

znyuk96 2년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말