Weird 문제 C언어 답안인데 시간초과 에러가 나오내요 확인좀 부탁드려요 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 이 알고리즘도 열심히 최적화만 하면 통과야 되겠지만, 더 효율적인 알고리즘을 쓰시는 게 좋습니다. 시간복잡도 분석을 해보면 O(sum(N_i))이므로 최대 제한을 대입해보면 시간 제한이 아슬아슬하겠죠. 8년 전 link mongoose 혹시 실례가 안된다면 더 효율적인 알고리즘이라는게 정확하게 어떤건지 알 수 있을까요 ??? 8년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
mongoose
Weird 문제 C언어 답안입니다.
답은 제대로 나오는데 시간 초과에러가 나오네요
혹시 시간을 줄일 수 있는 곳이 있는지 확인부탁드립니다.
시간을 줄이지 못할 경우에는 다시 짜도록 하겠습니다.
많은 답변 부탁드립니다.
봐주셔서 감사합니다.
8년 전