못생긴 수 구글 인터뷰 DP

못생긴 수란 오직 2,3,5만을 소인수로 가지는 수를 의미합니다. 다시 말해 오직 2,3,5를 약수로 가지는 합성수를 의미합니다. 1은 못생긴수라고 가정합시다. 따라서 못생긴 수들은 1,2,3,4,5,6,8,9,10,12,15 순으로 이어지게 됩니다. 이때 n번째 못생긴 수를 찾는 프로그램을 작성하세요 예를 들어 11번째 못생긴 수는 15입니다.

가능한 못생긴 수를 앞에서부터 하나씩 찾는 방법을 봅시다.

그리고 특징으로 못생긴수에 2,3,5를 곱하면 역시 못생긴 수가 됩니다.

n = int(input())

ugly = [0]*n #못생긴 수를 당기 위한 테이블(1차원 DP테이블)
ugly[0] = 1 #첫번째 못생긴 수는 1

#2,3,5배를 위한 인덱스
i2 = i3 = i5 = 0
#처음에 곱셈값을 초기화
next2,next3,next5 = 2,3,5

#1부터 n까지의 못생긴 수를 찾기
for l in range(1,n):
    #가능한 곱셈 결과 중에서 가장 작은 수를 선택
    ugly[l] = min(next2,next3,next5)
    #인덱스에 따라서 곱셈 결과를 증가
    if ugly[l] == next2:
        i2 += 1
        next2 = ugly[i2] * 2
    if ugly[l] == next3:
        i3 += 1
        next3 = ugly[i3] * 3
    if ugly[l] == next5:
        i5 += 1
        next5 = ugly[i5] * 5

#n번째 못생긴 수를 출력
print(ugly[n-1])

사실 코드만 봐서는 어떻게 작동하는지 잘 와닫지 않아서 많이 해맸는데 그냥 말로 쭉 설명을 해봅시다.

일단 우리는 못생긴 수를 순서대로 찾아보고 싶습니다. 그리고 못생긴수는 2와 3, 5로 이루어져있는 것이 특징이기에 이를 가지고 차례대로 구해볼 수 있습니다. 즉 어떤 못생긴수에다가 2,3,5를 곱하면 그 수 역시 못생긴 수가 되겠네요

일단 next2,3,5에는 2,3,5가 들어 있습니다. 그리고 ugly[0]은 1이 이미 들어 있으니 1부터 시작을 해봅시다.

ugly[1]에서 가장 작은 next값은 2가 됩니다. ugly[1]은 2로 변경이 되고 즉 두번째(인덱스1)의 못생긴 수는 2가 업데이트 되었습니다. 그러면 i2인덱스를 1증가 시키고 next2는 ugly[1]에서 2를 곱한 4가 됩니다. next는 4가 됬네요

그렇게 2번(3)도 똑같이 지나고 3번(4)차례가 되었습니다.

min에서 next의 값은 각각 4,5,6(2*3) 이 들어와 있고

ugly[3] 역시 next2 4와 같은 값을 가지고 있으니 인덱스에다가 2을 더하고 그러면 ugly[2] == 3 에다가 2를 곱한 다음 값은 next2 는 6으로 초기화가 되겠네요

이런 식으로 가장 작은 값을 순서로 2를 곱하고 3을 곱하고 5를 쭉 곱해보게 됩니다.

그리고 n번째 못생긴 수를 출력하면 끝