간단해서 그냥 완큐로 작성. 실행시간은 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]
}}}