35_못생긴 수

못생긴 수 = [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15.....]

2, 3, 5만 인수로 가지는 합성수(1포함)

 

못생긴 수에 2, 3, 5를 곱한 수도 못생긴 수다.

 

2의 배수 변수, 3의 배수 변수, 5의 배수 변수에 대해 각각 '가장 작은 못생긴 수'부터 오름차순으로 하나씩 확인하면서, 각 배수를 곱한 값도 '못생긴 수'가 될 수 있도록 처리하면 된다.

 

---

풀이 코드

# 못생긴 수
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])

 

아이디어 좋다.