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 네, 지수승의 시간 복잡도로는 해결하실 수 없을겁니다. 8년 전 link JongMan 그리고 시간초과가 나지 않아도 weild라고 쓰셔서 오답 나올 듯요.. 8년 전 link winterlood 우왓 감사합니다 !! 8년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
개잉룡
is함수가 sum이 n보다 큰경우에는 그 차 혹은 n을 key값으로 이용해서 key값보다 작은 약수들을 인덱스 0부터 시작해서 빼거나 빼지 않으면서 모든 부분집합의 차를 구하는 함수인데요 이게 아무래도 지수승의 시간복잡도를 가지니까 느린거같기도 한데 ㅠ 이런식으로 접근하면 안되는 건가요??
8년 전