WeirdNumber 시간초과 입니다.

  • skylife927
    skylife927

    어떻게 하면 시간초과를 줄일수 있을까요.
    Powerset를 활용하여 찾아봤는데..

    #include <iostream>
    
    using namespace std;
    
    int arr[100];
    int select1[100];
    int n=0;
    int result = 0;
    int mylength(int* arr){
        int i=0;
        while(arr[i] != 0){
            i++;
        }
        return i;
    }
    
    void process_solution(int k){
        int sum=0;
        for(int i=0; i<k; i++){
            if(select1[i] == 1){
                sum += arr[i];
            }
        }
        if(sum == n){
            result = 1;
        }   
    }
    
    void search(int s, int k){
        if(s==k){
            process_solution(k);
            return;
        }
        select1[s] = 0;
        search(s+1, k);
        select1[s] = 1;
        search(s+1, k);
    
    }
    
    void init(){
        result = 0;
        n=0;
    }
    
    
    
    int main(int argc, char** argv)
    {
        int test_case;
        int T;
    
        cin >> T;
        for(test_case = 0; test_case < T; test_case++)
        {
            //약수를 전부 구하자 
            //나눠지는 수를 가지고 배열에 넣장 ㅎㅎ
            init();
            cin>>n;
    
    
            int i=0;
            int j=0;
    
            // 나눠 지는 수를 구했습니당 
            for(i=1; i<n; i++){
                if(n%i == 0) arr[j++] = i;
            }
            /*for(i=1; i*i < n; ++i){
                if(n % i == 0){
                    arr[j++] = i;
                    if(n / i != i)
                        arr[j++] = n/i;
                }
            }*/
    
    
            // power set를 활용하여 n값에 도달하는지 확인합시당~
            int length = mylength(arr);
    
            search(0, length);
            if(result == 1){
                cout<<"not weird"<<endl;
            } else {
                cout<<"weird"<<endl;
            }
        }
    
        return 0;
    }
    

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

    전처리 + 0/1 knapsack을 풀 때 사용하는 동적 계획법을 이용하시면 될 것 같습니다.


    8년 전 link
  • skylife927
    skylife927

    확인 감사합니다. powerset이 아닌 dp방법을 고려해봐야겠군요.


    8년 전 link
  • seico75
    seico75

    arr 초기화를 안하신 것 같은데, mylength 가 정상 동작하지 않을 것으로 보입니다. 앞에서 구한 j값으로부터 length 를 구하도록 수정하는 것이 논리적으로보나 속도로 보다 맞다고 생각됩니다.
    약수를 구할때 n 까지 돌 필요가 있을까요? 만약 2 가 약수라고 하면 n/2 도 약수이며, i는 n/2 까지만 돌아도 충분할껍니다. 그렇게 for 의 범위를 동적으로 조정하면 더 빨라질 것 같네요.
    powerset은 조합을 만들고 나서 판단하는데, 중간에 n값보다 커지는 경우가 있을 수 있기 때문에 prunning?? early termination ?? 을 쓰는 것이 유리해보이고요. 또 powerset 은 합이 n인 경우를 찾아도 바로 빠져나오지 못하는 것으로 보입니다. 이부분도 개선하면 속도에 큰 도움이 될 것으로 보이네요..


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