[이코테 Ch16-35] 못생긴 수

👩🏻‍💻문제설명

[이코테 Ch16-35] 못생긴 수

못생긴 수란, 소인수분해 했을 경우 나오는 소인수가 2, 3 그리고 5뿐인 수를 이야기 하며, 이를 수열로 늘어놓으면 다음과 같다.

1, 2, 3, 4, 5, 6, 8, 9, 10, 12…

편의상 1을 못생긴 수에 포함한다. 정수 n이 주어졌을 때, n번째 못생긴 수를 출력하는 프로그램을 작성하라.

✍️Idea Sketch

시간복잡도

O(nlogn)

heap 라이브러리의 배열 원소 추가/삭제 시간복잡도는 O(logn)이다. 이를 고려하면 총 시간복잡도는 O(nlogn)이다.

알고리즘 : 다이나믹 프로그래밍

✍️내 소스코드

전체 코드

  import sys
  import heapq
  si = sys.stdin.readline

  n = int(si())
  queue = [2, 3, 5]
  dp = [1]

  while len(dp) < n:
    x = heapq.heappop(queue)
    if x == dp[-1]:
    continue

    dp.append(x)
    heapq.heappush(queue, x*2)
    heapq.heappush(queue, x*3)
    heapq.heappush(queue, x*5)

  print(dp[-1])