WEIRD 관련 질문드립니다.

  • Usagination
    Usagination

    WEIRD

    맨 처음에 약수를 모두 구하고 itr 벡터에 값을 복사해 부분집합을 만들어 Weird 여부를 판별하고 있습니다...만 시간 제한에 걸려 난처한 상황입니다.
    제 능력으론 더 이상 어디를 건드려야 좋을지 감이 안와서 이 방식이 너무 비효율적이라 아예 방향을 잘못 잡고 있는건 아닌가 하는 생각까지 드네요.
    소스 봐주시고 평가 해주시면 감사하겠습니다(__)

    #include <iostream>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    vector<int> itr;
    vector<int> divs;
    
    void GetDivisors(int num)
    {
        divs.clear();
    
        // 1은 모든 수의 약수
        divs.push_back(1);
    
        for (int i = 2; i*i < num; i++)
        {
            // 나누어 떨어지면 약수
            if (num%i == 0)
            {
                divs.push_back(i);
                divs.push_back(num / i);
            }
        }
    }
    
    int Combine(int number, vector<int>itr)
    {
        int sum = 0;
        for (std::vector<int>::iterator j = itr.begin(); j != itr.end(); ++j)
        {
            sum += *j;
        }
        if (sum > number) // 더한 값이 원래 수보다 크면 유사완전수 아님
            return 0;
        else if (number == sum) // 유사완전수라면 리턴
            return 1;
        else
            return -1;
    
    }
    
    int Verfiy(int number, int vStart, int nE)
    {
        for (; vStart <= divs.size() - nE; vStart++)
        {
            itr[itr.size() - nE] = divs[vStart];
    
            if (nE <= divs.size() && nE > 1)
            {
                auto verfiy = Verfiy(number, vStart + 1, nE - 1);
                if (verfiy) return verfiy;
            }
            else
            {
                auto combine = Combine(number, itr);
                if (combine) return combine;
            }
        }
        return 0;
    }
    
    int isWeirdNumber(int number)
    {
        GetDivisors(number);
    
        for (int i = divs.size() - 1; i >= 0; i--)
        {
            itr.clear();
            for (int j = 0; j <= i; j++) itr.push_back(-1);
    
            auto verfiy = Verfiy(number, 0, i + 1);
            if (verfiy) return verfiy;
        }
    
        return false;
    }
    
    int main()
    {
        int cases;
        cin >> cases;
        for (int i = 1; i <= cases; i++)
        {
            int number;
            cin >> number;
    
            cout << (isWeirdNumber(number) == 1 ? "not weird" : "weird") << endl;
        }
    
        return 0;
    }
    

    9년 전
2개의 댓글이 있습니다.
  • Being
    Being
    1. 위와 같이 하면 약수의 개수에 대해 지수적으로 동작하게 되므로, 시간 제한 안에 답이 나오지 않을 것입니다.
    2. 그와 별개로 vector<int>가 매 호출마다 복사되고 있는 점 역시 불필요한 시간복잡도 증가를 불러옵니다.
    3. \sqrt{n} 이 약수일 때 제대로 동작하지 않겠네요.

    9년 전 link
  • Usagination
    Usagination

    조언 감사드립니다!


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