[이코테] 다이나믹 프로그래밍_못생긴 수 (python) (다시 풀어보자)

문제

나의 풀이

1. 성공

• 아이디어
  : 2, 3, 5의 곱으로 이루어진 수가 오름차순 배열된다. 근데 다른 인수는 가지면 안된다.
  : 2만 쭉쭉 곱해나간 수, 3만 쭉쭉 곱해나간 수, 5만 쭉쭉 곱해나간 수를 정렬하면 끝.

n = int(input())
ugly = [0] * (n + 1)
ugly[1] = 1 # 첫번째 못생긴 수 = 1
two = three = five = 1 # 인덱스 출발
next2, next3, next5 = 2, 3, 5 # 처음 시작 수
for i in range(2, n + 1):
    ugly[i] = min(next2, next3, next5) # 오름차순이니까
    
    if ugly[i] == next2:
        two += 1
        next2 = ugly[two] * 2
    if ugly[i] == next3:
        three += 1    
        next3 = ugly[three] * 3
    if ugly[i] == next5:
        five += 1
        next5 = ugly[five] * 5
        
print(ugly[n])

• 맞왜틀이라 답지를 봤더니 답지와 99퍼 유사. 근데 실패함. why?? -> 성공
  : for i in range(1, n + 1): -> for i in range(2, n + 1):로 바꿈

2. 음 포기

• 아이디어: 그냥 다 곱해서 때려박고 set 해서 중복 제거 후 sort를 하려 했으나..너무 시간도 메모리도 많이 걸릴 뿐더러, 귀찮아서 포기