[이코테] 못생긴 수

문제

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

입력 조건

첫째 줄에 n이 입력됩니다. ($1 \leq n \leq 1,000$)

출력 조건

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

입출력 예

Example 1:

Input: 
10
Output: 
12

Example 2:

Input:
4
Output:
4

풀이과정

내풀이

import heapq

n = int(input

# 우선 순위 큐 선언
q = []

# dp 테이블 생성
d = [0] * 1001
d[1] = 1
for i in range(2, n+1):
    x = d[i - 1]
    
    # 중복을 피하기 위함
    s1 = set([2*x,3*x,5*x])
    for j in list(s1):
        if j not in q:
            heapq.heappush(q,j)
    
    d [i] = heapq.heappop(q)


print(d[n])

heap에서 빼낼 때 앞이랑 같다면 할당안해주는 식으로 가도 좋을 것같음.

책 풀이

이 문제는 가능한 못생긴 수를 앞에서부터 하나씩 찾는 방법으로 해결할 수 있다. 못생긴 수들은 [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …]와 같이 끊임없이 존재한다. 이때 못생긴 수에 2, 3 혹은 5를 곱한 수 또한 ‘못생긴 수’에 해당한다는 점이 포인트이다.

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

예를 들어 먼저 못생긴 수로 1이 있다고 해보자. 이때 각각 2의 배수, 3의 배수, 5의 배수를 구하면 다음과 같다.

• 2의 배수: 1 x 2 = 2
• 3의 배수: 1 x 3 = 3
• 4의 배수: 1 x 4 = 4

이로써 우리는 새롭게 2, 3, 4 또한 못생긴 수에 해당한다는 것을 알 수 있다. 따라서 이를 고려했을 때, 전체 못생긴 수는 {1, 2, 3, 4}가 된다.

첫 번째로 못생긴 수인 1에 이어서 그다음으로 못생긴 수는 2가 된다. 이때 각각 2의 배수, 3의 배수, 5의 배수를 구하면 다음과 같다.

• 2의 배수: 2 x 2 = 4
• 3의 배수: 2 x 3 = 6
• 4의 배수: 2 x 4 = 8

이로써 우리는 4, 6, 8이 못생긴 수에 해당한다는 것을 알 수 있다. 따라서 이를 고려했을 때, 전체 못생긴 수는 {1, 2, 3, 4, 6, 8}이 된다. 이렇게 못생긴 수들을 작은 수부터 차례대로 확인하면서, 각 못생긴 수에 대해서 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])