못생긴 수

출처:: 구글 인터뷰

분류:: DP

 

1. 문제 이해 및 해결과정

- 못생긴 수: 2,3,5만을 소인수로 가지는 수  - 1은 못생긴 수라고 가정  - 못생긴 수 = {1,2,3,4,5,6,8,9,10,12,15, ... }

 

2. 풀이방법

 1.DP

#못생긴 수
#
import sys
sys.stdin = open("input.txt","r")
n=int(input())

ugly = [0]*n #못생긴 수를 담기 위한 테이블(1차원 dp테이블)
ugly[0]=1 #첫번쨰 못생긴 수는 1

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

#처음에 곱셈값을 초기화
next2,next3,next5=2,3,5

#1부터 n까지의 못생긴 수 찾기
for i in range(1,n):
    #가능한 곱셈 결과 중에서 가장 작은 수를 선택
    ugly[i] = min(next2,next3,next5)
    #인덱스에 따라서 곱셈 결과를 증가
    if ugly[i]==next2:
        #print(i2,next2)
        i2+=1
        next2=ugly[i2]*2
    if ugly[i] == next3:
        #print(i3,next3)
        i3 += 1
        next3 = ugly[i3] * 3
    if ugly[i] == next5:
        i5 += 1
        next5 = ugly[i5] * 5
    print(ugly)
print(ugly[n-1])

 

3. 오답원인

 

4. 알게된 점