WEIRD 문제의 메모리 문제에서 막히고 있습니다.

  • novorobo2
    novorobo2

    처음으로 질문 드립니다.

    문제 : WEIRD

    WEIRD

    200이하의 자연수 집합에서
    약수(자기자신제외) 전체의 합이 자신보다 크지만
    어떤 약수의 부분집합의 합도 자신과 같지 않은 수를 찾는 문제 입니다.

    알고리즘

    • 주어진 숫자의 약수 집합을 구한다
    • 약수의 합을 체크한다
    • 약수 집합의 전체 부분집합을 구한다
    • 각각의 부분집합의 합을 체크해서 판별한다

    현재 소스코드

    import math
    import gc
    
    num = int(input())
    
    def getDevisors(n):
        res = []
        for i in range(1, int(math.sqrt(n)+1)):
            if n % i is 0:
                res.append(i)
                if i is not 1 and n / i != i:
                    res.append(int(n/i))
        res.sort()
        return res
    
    def subsets(my_set, n):
        result = [[]]
        for x in my_set:
            result = result + [y + [x] for y in result]
            for y in result:
                if sum(y) is n:
                    print("not weird")
                    return
        print("weird")
        return 
    
    for i in range(num):
        n = int(input())
        devisors = getDevisors(n)
        k = len(devisors)
        sd = sum(devisors)
        isNotWeird = 0
        if sd <= n:
            print("not weird")
            continue
        else :
            subsets(devisors, n)
        gc.collect()
    

    문제상황

    RTE (SIGKILL: program was forcefully killed, probably memory limit exceeded)
    이라는 오류를 계속 만나고 있습니다.
    함수 밖에서 gc를 하는건 별로 의미는 없을 것 같지만 시도해보았습니다.

    예상 문제지점

    약수집합의 전체 부분집합을 구하는 과정에서 메모리가 넘는 것으로 짐작됩니다만 어떤 식으로 이를 해결해야할지 잘 모르겠습니다.
    tracemalloc 등으로 체크해보았을 때에는 이 지점에서 3300B 가량을 사용하는 것으로 뜨는데 제한을 넘지는 않을 것 같습니다. 정확하게 판단이 되지 않아서 질문을 올리게 되었습니다.

    해결하려면 접근 전략 자체를 바꿔야 하는지, 아니면 약간의 트릭으로 해결될 수 있는 문제인지 조언을 구하고자 합니다.

    감사합니다.


    9년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    입력 숫자의 크기가 최대 50만까지이므로, 모든 부분집합을 다 확인하실 수는 없습니다.


    9년 전 link
  • novorobo2
    novorobo2

    그렇군요, 감사합니다 ㅠ 그 부분을 체크하지 못했네요. 다시 풀어보겠습니다.


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