importmathfromitertoolsimportcombinationsT=int(raw_input().strip())fortinxrange(T):N=int(raw_input().strip())### Find divisorsdivisors=[]divisors.append(1)sqrtN=int(math.sqrt(N))foriinxrange(2,sqrtN):ifN%i==0:divisors.append(i)ifi*i!=N:divisors.append(N/i)### Get sum of divisorssumDiv=sum(divisors)weird=FalseifsumDiv>N:weird=Truei=1### For each subset, calculate the sumwhilei<len(divisors):forcincombinations(divisors,i):ifsum(c)==N:weird=Falsei=len(divisors)breaki+=1ifweird:print'weird'else:print'not weird'
Divisor 을 구하는거까지는 괜찮은거같은데요.
그후에 subset 의 sum 을구하는대서 오래걸려요.
위에 코드는 콤비네이션 라이브러리를 쓴거구요.
다이나믹프로그래밍으로도 접근해봤는데 비슷하게 오래걸리네요.
어떻게 접근하는게 좋을까요?
develoken
Divisor 을 구하는거까지는 괜찮은거같은데요.
그후에 subset 의 sum 을구하는대서 오래걸려요.
위에 코드는 콤비네이션 라이브러리를 쓴거구요.
다이나믹프로그래밍으로도 접근해봤는데 비슷하게 오래걸리네요.
어떻게 접근하는게 좋을까요?
9년 전