WEIRD 시간초과 질문입니다.

  • develoken
    develoken
    import math
    from itertools import combinations
    
    T = int(raw_input().strip())
    
    for t in xrange(T):
    
        N = int(raw_input().strip())
    
        ### Find divisors
        divisors = []
        divisors.append(1)
    
        sqrtN = int(math.sqrt(N))
        for i in xrange(2, sqrtN):
            if N % i == 0:
                divisors.append(i)
                if i * i != N:
                    divisors.append(N/i)
    
        ### Get sum of divisors
        sumDiv = sum(divisors)
    
        weird = False
        if sumDiv > N:
            weird = True
            i = 1
    
            ### For each subset, calculate the sum
            while i < len(divisors):
                for c in combinations(divisors, i):
                    if sum(c) == N:
                        weird = False
                        i = len(divisors)
                        break
                i += 1
    
        if weird:
            print 'weird'
        else:
            print 'not weird'
    

    Divisor 을 구하는거까지는 괜찮은거같은데요.
    그후에 subset 의 sum 을구하는대서 오래걸려요.
    위에 코드는 콤비네이션 라이브러리를 쓴거구요.
    다이나믹프로그래밍으로도 접근해봤는데 비슷하게 오래걸리네요.
    어떻게 접근하는게 좋을까요?


    9년 전
1개의 댓글이 있습니다.
  • develoken
    develoken

    C++ 로 하니까 되네요.


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