weild문제 시간초과 단축을 어떻게해야할지 감을 못잡겠어요 ㅠ

  • 개잉룡
    개잉룡
    #include<iostream>
    #include<cmath>
    using namespace std;
    
    int compare(const void* a,const void* b) {
        int* tempa = (int*)a;
        int* tempb = (int*)b;
        return  *tempa - *tempb ;
    }
    
    void is(int parr[], int pidx, int fidx, int key,bool *pbool) {
        if (key == 0) {
            *pbool = true;
        }
        else if (key < 0)return;
        else if (fidx > pidx) {
            return;
        }
        else {
            is(parr, pidx, fidx + 1, key, pbool);
            is(parr, pidx, fidx + 1, key - parr[fidx], pbool);
        }
    }
    
    int main() {
        int k;
        cin >> k;
        while (k--) {
            int n;
            bool greater = false;
            int temp=0;
            cin >> n;
            double sqr = sqrt(n);
            int *arr = new int[((int)sqr * 2)+1];
            int arrtemp = 0;
            int sum = 1;
            arr[arrtemp++] = 1;
            if (((int)sqr*(int)sqr) == n) {
                sum += sqr;
            }
            for (int i = 2;i < sqr;i++) {
                if (n%i == 0) {
                    arr[arrtemp++] = i;
                    arr[arrtemp++] = (n / i);
                    sum += i;
                    sum += (n / i);
                }
            }
            if (sum >= n) {
                greater = true;
            }
            if (!greater)
                cout << "not weild" << endl;
            else
            {
                qsort(arr, arrtemp, sizeof(int),compare);
                if ((sum - n) > n) {
                    temp = n;
                }
                else {
                    temp = sum - n;
                }
                int idx=0;
                for (idx;arr[idx] < temp&&idx <= arrtemp;idx++);
                bool check = false;
                    is(arr, idx, 0, temp,&check);
                if (check)
                    cout << "not weild" << endl;
                else
                    cout << "weild" << endl;
            }
        }
        return 0;
    }
    

    is함수가 sum이 n보다 큰경우에는 그 차 혹은 n을 key값으로 이용해서 key값보다 작은 약수들을 인덱스 0부터 시작해서 빼거나 빼지 않으면서 모든 부분집합의 차를 구하는 함수인데요 이게 아무래도 지수승의 시간복잡도를 가지니까 느린거같기도 한데 ㅠ 이런식으로 접근하면 안되는 건가요??


    8년 전
3개의 댓글이 있습니다.
  • JongMan
    JongMan

    네, 지수승의 시간 복잡도로는 해결하실 수 없을겁니다.


    8년 전 link
  • JongMan
    JongMan

    그리고 시간초과가 나지 않아도 weild라고 쓰셔서 오답 나올 듯요..


    8년 전 link
  • winterlood
    winterlood

    우왓 감사합니다 !!


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