글 읽기 - [c++] 시간초과(유클리드 호제법 사용했음)

lucete171 3년 전 0

일단 입력받은 수들의 차들의 최대공약수의 약수들을 출력하는 것이 목적입니다

gcd사용횟수가 많더라도 41줄의 i가 커지면 커질수록 gcd출력 속도가 빨라져서 상관없을 것 같은데 어디서 시간 초과가 발생하는 걸까요?

약수 출력인가요..?

#include <iostream>
using namespace std;

int abs(int a){
	if(a>=0)
	{
		return a;
	}
	else
	{
		return (-a);
	}
}

int small(int a,int b){
	if(a>b)
	{
		return b;
	}
	else
	{
		return a;
	}
}

int gcd(int a,int b){
	int x=small(a,b);
	int y=a+b-x;
	if(y%x==0)
	{
		return x;
	}
	else
	{
		return gcd(x,y%x);
	}
}

int gcdlist(int *arr,int n){
	int g=arr[0];
	for(int i=1;i<n;i++)
	{
		g=gcd(arr[i],g);		
	}
	return g;
}

int main()
{
    int n;
    cin>>n;
    int arr[n-1];
    int tmp;
    for(int i=0;i<n;i++)
    {
    	int a;
    	cin>>a;
		if(i!=0)
		{
			arr[i-1]=abs(a-tmp);
		}
		tmp=a;
	}
	int g=gcdlist(arr,n-1);
	for(int i=2;i<=g;i++)
	{
		if(g%i==0)
		{
			cout<<i<<" ";
		}
	}
    return 0;
}

lucete171 3년 전 0

마지막에 약수구하는 거 시간 줄여보려고

g가 짝수라면 1,2,...,g/2,g

홀수라면 1,a,...,g/a,g(a는 2보다 큰 g의 약수)

이때 g/a는 g/2보다 작기 때문에 짝수든 홀수든 g/2 까지만 i++시키고

g만 따로 출력해주면 g/2만큼 for문을 덜 돌 수 있을 거 같아서 해봤는데 맞았습니다가 뜨긴 뜨네요

그래도 시간은 오래 걸리는 것 같은데 더 줄일 수 있는 곳은 없을까요?

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

문제

문제

출처

ICPC

[c++] 시간초과(유클리드 호제법 사용했음)

lucete171 3년 전 0

lucete171 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말