[다이나믹 프로그래밍] 이코테 (파이썬) 못생긴 수 풀이

[문제]

못생긴 수란 오직 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])

 

---

출처

이것이 코딩 테스트다 with 파이썬 - 나동빈 저