간단해서 그냥 완큐로 작성. 실행시간은 0.1초 이하.
~cpp
from bisect import bisect
prim=(2,3,5)
def ugly(n,ugs=None):
if not ugs: ugs=[1]
while len(ugs)<n:
tris=[bisect(ugs,lastug/p)
for lastug,p in zip([ugs[-1]]*len(prim),prim)]
ts=[ugs[ind]*mul for ind,mul in zip(tris,prim)]
ugs.append(min(ts))
return ugs
if __name__=='__main__':
assert ugly(11)==[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15]
print "The 1500'th ugly number is",ugly(1500)[-1]
