Weird 문제 C언어 답안인데 시간초과 에러가 나오내요 확인좀 부탁드려요

  • mongoose
    mongoose

    Weird 문제 C언어 답안입니다.
    답은 제대로 나오는데 시간 초과에러가 나오네요
    혹시 시간을 줄일 수 있는 곳이 있는지 확인부탁드립니다.
    시간을 줄이지 못할 경우에는 다시 짜도록 하겠습니다.

    #include <stdio.h>
    #include <stdlib.h>
    
    #define TRUE  1
    #define FALSE 0
    
    void setOfDivs(int num, int *arr, int *index);
    int sumOfDivs(int *arr, int index);
    void isWeirdNum(int num, int *arr, int sum, int index, int indexOfSub);
    
    int flag = 0;
    
    int main(void)
    {
        int count;
        int *num;
        int arr[500000] = {0, };
        int i;
        int index;
        int sum;
    
        scanf("%d", &count);
        num = (int *) malloc(sizeof(int) * count);
        for(i = 0 ; i < count ; i++)
        {
            scanf("%d", &num[i]);
        }
    
        for(i = 0 ; i < count ; i++)
        {
            index = 0;
            flag = 0;
    
            // num[i] : Weird Number인지 확인 | arr : Divisors Set | index : # of Divisors
            setOfDivs(num[i], arr, &index);
    
            // 1st. sumOfDivs > num[i] ?
            sum = sumOfDivs(arr, index);
            if(num[i] >= sum)
            {
                printf("not weird\n");
                continue;
            }
    
            // 2st. sumOfSubset == num[i] ?
            isWeirdNum(num[i], arr, sum, index, 0);
            if(flag)
            {
                printf("not weird\n");
            }
            else
            {
                printf("weird\n");
            }
        }
    }
    
    void setOfDivs(int num, int *arr, int *index)
    {
        int i;
    
        for(i = 1 ; i < num ; i++)
        {
            if((num % i) == 0)
            {
                arr[*index] = i;
                *index = *index + 1;
            }
        }
    }
    
    int sumOfDivs(int *arr, int index)
    {
        int i;
        int sum = 0;
    
        for(i = 0 ; i < index ; i++)
        {
            sum += arr[i];
        }
    
        return sum;
    }
    
    void isWeirdNum(int num, int *arr, int sum, int index, int indexOfSub)
    {
        int i;
    
        if(num == (sum - arr[indexOfSub]))
        {
            flag += TRUE;
        }
        else if(num > (sum - arr[indexOfSub]))
        {
            flag += FALSE;
        }
        else
        {
            for(i = indexOfSub + 1 ; i < index ; i++)
            {
                isWeirdNum(num, arr, sum - arr[indexOfSub], index, i);
            }
        }
    }
    

    많은 답변 부탁드립니다.
    봐주셔서 감사합니다.


    8년 전
2개의 댓글이 있습니다.
  • kcm1700
    kcm1700

    이 알고리즘도 열심히 최적화만 하면 통과야 되겠지만, 더 효율적인 알고리즘을 쓰시는 게 좋습니다. 시간복잡도 분석을 해보면 O(sum(N_i))이므로 최대 제한을 대입해보면 시간 제한이 아슬아슬하겠죠.


    8년 전 link
  • mongoose
    mongoose

    혹시 실례가 안된다면 더 효율적인 알고리즘이라는게 정확하게 어떤건지 알 수 있을까요 ???


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