[Python] 못생긴 수

문제

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

입력

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

출력

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

입력 예제

11

출력 예제

15

문제 풀이

• 가장 작은 못생긴 수에 차례대로 2, 3, 5를 곱하면 다음 못생긴 수를 구할 수 있다.
• 따라서 각각 2, 3, 5를 곱한 인덱스와 2, 3, 5를 곱한 값을 변수에 저장 한 후, 연산한다.

코드

n = int(input())
ugly = [1] * n
# 첫번째 못생긴 수는 1
ugly[0] = 1

# 각각 다음 2,3,5를 곱할 인덱스
i2, i3, i5 = 0, 0, 0
# 2,3,5를 곱한 다음 못생긴 수
next2, next3, next5 = 2, 3, 5

for i in range(1, n):
    ugly[i] = min(next2, next3, next5)
    # 2를 곱한 값이라면, 2곱한 인덱스 값 카운트 후, 2를 곱한 다음 값 저장
    if ugly[i] == next2:
        i2 += 1
        next2 = ugly[i2] * 2
    # 3울 곱한 값이라면, 3곱한 인덱스 값 카운트 후, 3을 곱한 다음 값 저장
    if ugly[i] == next3:
        i3 += 1
        next3 = ugly[i3] * 3

    # 5를 곱한 값이라면, 5곱한 인덱스 값 카운트 후, 5를 곱한 다음 값 저장
    if ugly[i] == next5:
        i5 += 1
        next5 = ugly[i5] * 5

print(ugly[n - 1])