못생긴 수 - DP

 이해하는데 꽤 애먹은 문제였다. 풀이 자체는 굉장히 간단하다. 못생긴 수에 2,3,5 중 하나를 곱해준 결과는 항상 못생긴 수라는 것이다. 바꿔 말하면, 1부터 시작해서 2,3,5를 각각 곱해가며 못생긴 수를 만들고, 오름차순으로 나열해야 하니 후보 숫자들 중 최소값을 못생긴 수 배열 끝에 담아주는 것이다.

 next가 의미하는 것은, 모든 못생긴 수에 대해 2,3,5를 각각 곱해본다는 의미이다.

코드

n = int(input())

ugly = [0]*n
ugly[0] = 1

i2 = i3 = i5 = 0
next2,next3,next5 = 2,3,5

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]*3

print(ugly[n-1])