글 읽기 - 시간초과 이유

ppsrac 2년 전 0

안녕하세요. 저는 이 문제를 풀 때 n-1개의 차이의 gcd를 구하기 위해 분할정복(?)의 방식으로 최대한 빠르게 구하려고 하였습니다. 그럼에도 불구하고 시간초과가 떴는데, 일단 2~200까지 2의 배수를 넣은 것과 i*(i+1)*(i+2)꼴의 100개의 수를 넣었을 때는 굉장히 잘 나왔습니다. 혹시 어떠한 것이 문제일지 조언을 구할 수 있을까요?

감사합니다.

#include <stdio.h>
#include <stdlib.h>

int arr[100]={0};
int diff[100]={0};
void swap(int *a, int *b){
    int tmp;
    if (*a<*b){
        tmp=*a;
        *a=*b;
        *b=tmp;
    }
}
int gcd(int* arr, int l, int r){
    int mid=(l+r)/2;
    int n=r-l;
    int div1, div2;
    if(n==1){
        return arr[l];
    }
    div1=gcd(arr,l,mid);
    div2=gcd(arr,mid,r);
    swap(&div1,&div2);
    while(div2!=0){
        div1=div1%div2;
        swap(&div1,&div2);
    }
    return div1;
}
void divisor(int n){
    int i=2;
    for(;i<=n;i++){
        if(n%i==0){
            printf("%d ",i);
        }
    }
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",arr+i);
    }
    for(int i=0;i<n-1;i++){
        diff[i]=abs(arr[i+1]-arr[i]);
    }
    divisor(gcd(diff,0,n-1));
    return 0;
}

ppsrac 2년 전 0

생각해보니 divisor 함수가 gcd값이 큰 경우에 대해서 오류가 나겠네요...ㅋㅋㅋ

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

문제

문제

출처

ICPC

시간초과 이유

ppsrac 2년 전 0

ppsrac 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말