못생긴 수

문제

못생긴 수란 오직 2,3,5만을 소인수로 가지는 수를 의미한다. 1은 못생긴 수라고 가정한다. n번째 못생긴 수를 찾아라.

못생긴 수 : {1,2,3,4,5,6,8,9,10,12,15....}

 

입력

n (1 ~ 1,000)

 

출력

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

 

풀이

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])

다이나믹 프로그래밍 문제이다.

못생긴 수에 2,3,5를 곱한 수 또한 못생긴 수에 해당한다는 점이 포인트이다.

 

또한, ugly[l] = min(next2, next3, next5) 코드가 핵심인데, 오름차순으로 table을 유지하기 위해 못생긴 수에 2,3,5를 곱한 수 중 작은 수를 그 다음 못생긴 수로 설정해야 한다.