[dp/구글 인터뷰] 못생긴 수(다시)

2,3,5를 인수로 가지는 합성수를 못생긴 수라고 한다.

문제는 2,3,5로 이루어진 합성수를 순서대로 정렬했을 때, n번째 못생긴 수를 찾는 프로그램을 작성하는 것이다 

 

처음에는 집합계산하는 것처럼 일일이 다 집합 계산해서 교집합 빼는 걸로 생각했는데 이렇게 풀면 안될  것 같다. 

 

-정답풀이: 

아직 정답 풀이가 온전히 이해가지 않는다. 나중에 다시와서 봐야할 것 같다 

n=int(input())
ugly=[0]*n
ugly[0]=1
i2=i3=i5=0
next2,next3,next5=2,3,5

for x in range(1,n):
    ugly[x]=min(next2,next3,next5)
    if ugly[x]==next2:
        i2+=1
        next2=ugly[i2]*2
    if ugly[x]==next3:
        i3+=1
        next3=ugly[i3]*3
    if ugly[x]== next5:
        i5+=1
        next5=ugly[i5]*5
print(ugly[n-1])