못생긴 수

📌문제

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

 

📌풀이

못생긴 수에 2,3,5를 곱한 수 또한 못생긴 수에 해당

 

📌코드

n = int(input())

ugly = [0] * n  # 못생긴 수를 담기 위한 테이블
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

print(ugly[n - 1])

 

📌참고

https://g.co/kgs/eyd5SSd

이것이 취업을 위한 코딩 테스트다 with 파이썬