WEIRD를 푸는 알고리즘 질문드립니다.

  • Signin
    Signin

    WEIRD 문제를 풀고 있습니다.

    이 문제는 주어진 자연수 n에 대해서,
    이 자연수가 weird number인지 아닌지 판단하는 것입니다.

    weird의 조건은 아래와 같습니다.

    • n의 자신보다 작은 약수들의 총합이 n보다 크고,
    • 그 약수들 중에 몇 개를 어떻게 고르던지 그 합이 n이 될 수 없음.

    저는 비효율적인 방법으로 풀었는데요,
    풀고 나서, 훨씬 적은 수행시간이 드는 다른 분들의 코드를 보았으나
    보면서도 알고리즘이 이해가 가지 않아 질문드리게 되었습니다.

    아래 코드에서는
    1. 먼저 약수를 크기가 작은 순으로 리스트에 정렬시킨다.
    2. 리스트 내의 모든 수를 더한 값이 n보다 큰 동안 루프를 돌린다.
    LOOP :
    1) 현재 리스트 내 수의 총합에서 n을 뺀다.
    2) 약수들 중에, 1)에서 구한 값 이하인 약수 중 최대를 삭제한다.
    3. 남은 약수들의 합이 n과 같으면 not weird, 다르면 weird.

    이 알고리즘이 어떻게 '부분 합이 n이 될 수 있는가?'를
    판별할 수 있는 것일까요?

    #include<iostream>
    #include<list>
    #include<algorithm>
    #include<numeric>
    #include<math.h>
    using namespace std;
    
    int main()
    {
        int c;
        int sum;
    
        cin >> c;
    
        while(c){
            int n,sq;
            list<int> res;
    
            cin >> n;
            sq=(int)sqrt((double)n);
            if(n%sq==0){
                res.push_front(sq);
                if(sq!=n/sq)
                    res.push_back(n/sq);
            }
            for(int i=sq-1;i>1;i--){
                if(n%i==0){
                    res.push_front(i);
                    res.push_back(n/i);
                }
            }
            res.push_front(1);
    
            if(accumulate(res.begin(),res.end(),0)<n){
                cout << "not weird" << endl;
            }
            else{
                while((sum=accumulate(res.begin(),res.end(),0))>n){
                    list<int>::iterator iter;
                    list<int>::iterator iter2;
                    sum-=n;
                    for(iter=iter2=res.begin();iter!=res.end();iter++){
                        if(sum<*iter)
                            break;
                        iter2=iter;
                    }
                    res.erase(iter2);
                }
                if(sum==n)
                    cout << "not weird" << endl;
                else
                    cout << "weird" << endl;
            }
            c--;
        }
        return 0;
    }
    

    직접 값을 출력하면서 돌려보고서도 이해가 가지 않아
    질문드리게 되었습니다.
    알려주시면 감사하겠습니다~!


    10년 전
4개의 댓글이 있습니다.
  • A.I
    A.I

    제가 돌려본 결과(1만 이하의 모든 입력에 대해) 제가 예전에 작성한 솔루션과 결과가 상이한 것을 발견했습니다. 정확히는 1천 이상에서 weird가 아님에도 weird로 나오는 경우가 간혹 있었습니다.혹시 첨부하신 코드가 Accept 된 것이 맞는지 알 수 있을까요?


    10년 전 link
  • Signin
    Signin

    먼저 살펴봐주셔서 정말 감사합니다.
    첨부된 코드의 답안 번호는 #87095이구요,
    WEIRD문제에서 통과한 답안 중에
    수행시간이 빠른 순으로 정렬시 5번째에 오는 코드입니다.


    10년 전 link
  • Being
    Being

    음 반례가 엄청 많을 것 같이 생겼네요. 일반적인 수의 집합에 대해 subset sum 문제는 이런 식으로 풀 수 없다는 것이 알려져져 있는데, 이게 약수들의 집합이라고 별다른 특성이 있을 것이라 생각하기 어렵네요.


    10년 전 link
  • Signin
    Signin

    그렇군요.... 이 알고리즘이 어떻게 답을 찾을 수 있는지
    이해하지를 못해서 너무 답답했네요 ㅠㅠ
    알려주셔서 감사합니다~!


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