[이것이 코딩테스트다] 못생긴 수

🗃️문제 설명

못생긴 수란 오직 2, 3, 5 만을 소인수로 가지는 수를 의미한다. 다시 말해 오직 2, 3, 5를 약수로 가지는 합성수를 의미한다.

12의 약수인 1, 2, 3, 4, 6, 12 중에서 2와 3이 소인수이다. 1은 못생긴 수라고 가정한다.

따라서 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... } 순으로 이어지게 된다. 이 때, n번째 못생긴 수를 찾는 프로그램을 작성해라.

예를 들어 11번째 못생긴 수는 10이다.

첫째 줄에 n이 입력된다.(1 ≤ n ≤ 1,000)

n번째 못생긴 수를 출력한다.

🖥️코드

import sys
input = sys.stdin.readline

n = int(input())
lst = [0] * (n + 1)
lst[0] = 1

n2, n3, n5 = 2, 3, 5
idx2, idx3, idx5 = 0, 0, 0

for i in range(1, n+1):
    lst[i] = min(n2, n3, n5)
    if lst[i] == n2:
        idx2 += 1
        n2 = lst[idx2] * 2
    if lst[i] == n3:
        idx3 += 1
        n3 = lst[idx3] * 3
    if lst[i] == n5:
        idx5 += 1
        n5 = lst[idx5] * 5
print(lst)

🧠아이디어

알고리즘 유형 : 다이나믹 프로그래밍

가장 작은 수를 못생긴 수로 하고 못생긴 수에 해당한다면 다음 수를 미리 구해 초기화한다.

🔒문제 출처 및 참고 코드

이것이 코딩테스트다 with 파이썬 - 못생긴 수
모범 답안 - 못생긴 수