[이것이 코딩 테스트다] 못생긴 수 - 다이나믹 프로그래밍

문제

못생긴 수란 오직 2, 3, 5 만을 소인수로 가지는 수를 의미합니다.

1은 못생긴 수라고 가정합니다.

이때 n 번째 못생긴 수를 찾는 프로그램을 작성하십시오.

 

입력 조건

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

출력 조건

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

---

해결 과정

---

첫번째 아이디어이다.

선형탐색 과정에서 못생긴 수 찾기

1, 2, 3, 4, ..., n 순으로 탐색한다. 다시 말하면 1부터 n까지 선형탐색을 한다. 현재 위치의 수를 소인수분해해서 못생긴 수인지 파악하는 방법이다.

하지만 소인수분해를 계산해야하는 시간적 번거로움이 생긴다.

2, 3, 5로 나머지가 0이 아닐 때까지 나누는 함수를 만드는 것은 금방이다. 하지만 991번째 못생긴 수 부터 1000번째 못생긴 수를 보면, 소인수분해 계산에서 시간초과에 걸릴 수 있다고 생각했다.

* [ ..., 52488000, 52734375, 53084160, 53144100, 54000000, 54675000, 55296000, 55987200, 56250000, 56687040]
  991번째 못생긴 수 ~ 1000번째 못생긴 수

 

실제로 마지막 991번 째 못생긴 수(52,488,000)는 2^(6) x 3^(8) x 5^(3)이다. 2, 3, 5만 가지고 총 17번의 나눗셈 연산이 필요하다.

이 연산횟수는 어마어마한 총 연산 횟수를 불러온다. 못생긴 수 1000개가 필요하니, 5600만 단위까지 하나하나 소인수분해를 하면, 약 5600만 * 약 10회 = 약 5억 6000만

연산횟수가 5억회가 넘는다. PS에서는 CPU가 1초에 1억 회 연산한다고 가정한다. 그래서 이 방법은 약 5초의 시간이 걸리는 방법이고, 이 문제의 시간 제한(1초)를 무려 다섯 배나 웃도는 상황이다.

그러므로 이 방법은 채택하지 못한다.

---

두 번째 방법이다.

못생긴 수를 만들자. / 50을 넘어간 못생긴 수는 위 표에 나타내지 않았습니다.

'그럼 반대로 2, 3, 5만 가지고 못생긴 수를 만드는 것은 어떨까?' 에서 시작한 해결 방법이다.

소인수인 2, 3, 5 에 못생긴 수를 곱해가면 그것도 못생긴 수이다.

그래서 소인수와 못생긴 수를 계속 곱하면서 새로 못생긴 수를 추가한다.

 

1. 못생긴 수(ugly_num, 최초 2부터 시작)를 소인수들(2, 3, 5)과 곱한다.
2. 곱한 값을 못생긴 수 집합에 추가한다.
3. ugly_num 을 +1 증가시킨다.
4. 증가된 ugly_num 가 못생긴 수인지 확인한다.
5. 못생긴 수라면, 1번으로 돌아간다.
6. 못생긴 수 집합의 길이가 n보다 크거나 같아지면 반복을 종료한다.

* 못생긴 수를 집합(set)에 담는 이유는, gif 표를 보면 알 수 있듯이 같은 수를 여러 번 만들 수 있기 때문이다. (이미 색칠되어 있는 칸이 다른 색으로 변경된 것이 한 번 더 만들어졌다는 표현이다.)
* ugly_num 이 집합에 이미 추가된 못생긴 수라고 보장할 수 있다.

 

---

코드💻

 

# 못생긴 수
n = int(input())

ugly_set = set([1, 2, 3, 5])
ugly_num = 2
while len(ugly_set) < n:
    if ugly_num in ugly_set:
        ugly_set.add(2 * ugly_num)
        ugly_set.add(3 * ugly_num)
        ugly_set.add(5 * ugly_num)
    ugly_num += 1

uglys = sorted(list(ugly_set))

print(uglys[n-1])

---