못생긴 수 (재시도 필요)

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

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

ex : 1,2,3,4,5,6,8,9,10,12,15

n번째 못생긴 수 찾기.

 

부족한 점 : 어떻게 풀어야 할 지 감이 오지 않았다.

 

풀이 방법 :

키워드는 못생긴 수에 2,3,5를 곱한 수 또한 못생긴 수가 된다는 점이었다.

1*1=1

2*1=2

3*1=3

5*1=5

 

2*2=4

3*2=6

5*2=10

 

1. dp 테이블(ugly)를 n개로 초기화 한다. 첫번째 못생긴 수는 1이다.

2. 처음 곱셈값 (2,3,5)와 2,3,5배를 위한 인덱스(i2,i3,i5)를 변수로 따로 둔다.

처음의 곱셈값은 배수씩 증가시키면서 min을 이용해 순서대로 ugly테이블에 넣기 위해서 필요.

인덱스는 각 못생긴 수를 차례대로 2,3,5를 곱해서 만들기 위해서.

 

3. 1부터 n까지 먼저 ugly테이블의 i번째 값을 현재 곱셈값중 최소인 것으로 넣는다. ( 오름차순으로 ugly테이블에 못생긴 수를 넣기 위해서)

그 후 선택된 곱셈값이 어떤 수의 배수인지 조건문으로 찾아서 그 수에 맞는 2,3,5배 인덱스(i2,i3,i5)를 하나 증가시키고, 곱셈값을 업데이트 한다.

이 때 ugly테이블의 인덱스를 2,3,5배 인덱스(i2,i3,i5)로 해준다. 왜? 못생긴 수에 2,3,5를 곱해도 못생긴 수가 되므로 

이 원리를 이용해서,  어차피 min때문에 오름차순으로 들어가기 때문에 ,ugly테이블에 있는 값을 차례대로 사용하고, 중복을 피하려고 사용한것 같다.

 

 

 

 

#1. 몇번째 못생긴 수인지 입력받기
n=int(input())
#테이블 만들기
ugly=[0]*n
ugly[0]=1#첫번째 수는 1

#2,3,5배 인덱스
i2=i3=i5=0

#초기 곱셈값
next2,next3,next5=2,3,5


for i in range(1,n):
  ugly[i]=min(next2,next3,next5)

  if ugly[i]==next2:
  i2+=1
  next2=ugly[i2]*2
  if ugly[i] == next3:
  i3 += 1
  next3 = ugly[i3] * 3
  if ugly[i] == next5:
  i5 += 1
  next5 = ugly[i5] * 5

print(ugly[n-1])