[이코테] Q35 DP_못생긴 수(8.23)

문제

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

합성수를 의미합니다. 1은 못생긴 수라고 가정합니다. 따라서 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...} 순으로

이어지게 됩니다. 이때, n번째 못생긴 수를 찾는 프로그램을 작성하세요. 예를 들어 11번째 못생긴 수는 15입니다.

[입력 조건]

1. 첫째 줄에 N이 입력됩니다. (1 <= n <= 1,000)

[출력 조건]

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

<입력 예시 1>
10
<출력 예시 1>
12

<입력 예시 2>
4
<출력 예시 2>
4

문제풀이

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])
Footer
© 2022 GitHub, Inc.
Footer navigation