weird number 질문입니다.!!

  • 2000spot
    2000spot

    unsigned int arr[100];
    unsigned int elements[MAX+1];

    unsigned int number;
    unsigned int count;
    unsigned int subset_check;

    //qsort를 이용하기 위한 포인터 함수
    int compare(const void * a, const void * b) {
    if(*(int*)a>(int)b)
    return 1;
    else if(*(int*)a==*(int*)b)
    return 0;
    else
    return -1;
    }

    void subset_sum(unsigned int sum, unsigned int from) {
    if(sum==number) {
    subset_check = FALSE;
    return;
    }

    for(unsigned int i=from ; i<count ; i++) {
        if(arr[i]+sum > number)
            return;
    
        subset_sum(arr[i]+sum, i+1);
    
        if(subset_check == FALSE)
            return;
    }

    }

    int main() {
    unsigned int n;
    unsigned int sum;
    number = 1;
    scanf("%u", &n);

    while(n!=0) {
        n--;
    
        //초기화
        memset(arr, 0, number*sizeof(int));
        memset(elements, 0, number*sizeof(int));
        count=0;
        subset_check = TRUE;
    
        arr[count++]=1;
        sum=1;
    
        scanf("%u", &number);
    
        for(unsigned int i=2; i<=number/2 ; i++) {
            // 약수를 찾을 때 반복을 줄이기 위함
            if(number%i == 0 && elements[i]==0) {
                //n*n의 형태일 때
                if(number/i == i) {
                    arr[count++]=i;
                    sum+=i;
                    elements[i]=1;
                }
                //n*n의 형태가 아닐때
                else {
                    arr[count++]=i;
                    arr[count++]=number/i;
                    sum+=i + number/i;
                    elements[i]=1;
                    elements[number/i]=1;
                }
            }
        }
        qsort((void *)arr, count, sizeof(unsigned int), compare);
    
        //조건1
        if(sum > number) {
            //조건 2
            subset_sum(0, 0);
            if( subset_check == TRUE) {
                printf("weird\n");
            }
            else {
                printf("not weird\n");
            }
        }
        else {
            printf("not weird\n");
        }
    }
    
    return 0;

    }

    이 소스는 그냥 첨부한 거고요.. 최대한 필요없는 가지는 탐색을 안할려고 했거든요. 근데 계속 런타임 오류나는 거 보니까 이것은 백트랙킹으로 하는게 아닌거같은데요... 제가 잘못 생각하고 있는건가요? 시간을 더 줄일방법이 있나요? 수학 식을 사용해야하나요....


    3년 전
2개의 댓글이 있습니다.
  • 맥커터
    맥커터

    런타임 오류는 시간초과와는 상관 없지 않나요?
    시간을 줄이기 이전에 런타임 오류부터 해결하셔야 할듯 합니다


    3년 전 link
  • astein
    astein

    문제에서 주어진 제한들(특히 C)을 확인해 보세요.


    3년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.