[동적계획법] 난이도1.5, Google 인터뷰 '못생긴 수' (Python)

<문제>

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

 

<입력 조건>

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

<출력 조건>

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

---

<문제 풀이>

1. 1부터 1000까지 2,3,5를 약수로 가지는 수 구하기
2. 2부터 1000까지 2,3,5 이외에 약수를 가지는 합성수를 제거하기
3. n번째 못생긴 수 구하기

<코드>

'''입력 예시
11

10

4
'''

n = int(input())

d[1] = 1
for i in range(1001):
    if i%2==0 or i%3==0 or i%5==0:
        d[i] = i

for i in range(2,1001):
    if i%2==0:
        if d[i//2]==0:
            d[i] = 0
    if i%3==0:
        if d[i//3]==0:
            d[i] = 0
    if i%5==0:
        if d[i//5]==0:
            d[i] = 0

count = 0
for i in range(1,1001):
    if d[i]!=0:
        count += 1
    if count == n:
        print(d[i])
        break

 

#답

n = int(input())

ugly = [0] * n
ugly[0] = 1

i2 = i3 = i5 = 0
next2, next3, next5 = 2, 3, 5

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] == next2:
    	i3 += 1
        next3 = ugly[i3]*3
    if ugly[l] == next2:
    	i5 += 1
        next5 = ugly[i5]*5
        
print(ugly[n-1])

 

<고쳐야 할 점>

• 알고리즘 다시 설계하기
• 문제랑 답 이해하기
• 복습 알고리즘