Weird number 문제 관련 질문이 있습니다

  • uyen
    uyen

    일단 코드는 다음과 같습니다

    #include<iostream>
    #include<vector>
    using namespace std;
    
    int divisor[1000];
    bool checkEqual(int num, int index);    //약수 조합의 합이 같은지 아닌지 판단
    
    int main()
    {
        int T, num, sumDiv;
        int index;
        bool isequal;
    
        cin >> T;
        while(T-- > 0){
            cin >> num;
    
            isequal = true;
            if(num%2 == 0){
                index = 0;
                sumDiv = 0;
                for(int i = 1; i*2 <= num; i++){
                    if(num%i == 0){
                        divisor[index++] = i;
                        sumDiv += i;
                    }
                }
                if(sumDiv > num)
                    isequal = checkEqual(num, index-1);
            }
    
            if(isequal)
                cout << "not weird" << endl;
            else
                cout << "weird" << endl;
        }
    }
    
    bool checkEqual(int num, int index)
    {
        int i;
        for(i = index; i >= 0; i--){
            if(divisor[i] <= num)
                break;
        }
    
        if(i < 0)
            return false;
    
    
        if(num-divisor[i] == 0)
            return true;
    
        for(int j = i; j >= 0; j--){
            for(int k = j-1; k >= 0; k--){
                if(checkEqual(num-divisor[j], k))
                    return true;
            }
        }
        return false;
    }
    
    
    bool checkEqual(int num, int index)
    {
        int i;
        for(i = index; i >= 0; i--){
            if(divisor[i] <= num)
                break;
        }
    
        if(i < 0)
            return false;
    
        if(num-divisor[i] == 0)
            return true;
    
        if(checkEqual(num-divisor[i], i-1))
            return true;
        else
            return checkEqual(num, i-1);
    }
    

    그리고 제가 checkEqual 함수를 두개 만들어봤는데 위에꺼는 시간 초과이고 아래는 110ms정도만에 통과하던데요
    똑같은 알고리즘으로 구현한것 같은데 시간이 20배가 넘게 차이가 나네요...
    저도 모르게 다른 알고리즘을 쓴건지.. 아니면 다른 이유가 있는건지 알려주시면 감사하겠습니다


    10년 전
3개의 댓글이 있습니다.
  • Kureyo
    Kureyo

    ~code c++로 묶어주세요 ㅠㅠ


    10년 전 link
  • uyen
    uyen

    깜빡했네요 죄송합니다 ㅋㅋ


    10년 전 link
  • JongMan
    JongMan

    본인도 모르게 다른 알고리즘을 쓰신 것이 맞습니다.

    전자에서는 같은 인자를 갖는 checkEqual()이 여~~~~러번 호출되게 됩니다.
    한번 checkEqual()이 한번 호출될 때마다 printf()를 해보시면 확 느낌이 오실겁니다.


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