[이취코] DP 실전 - 못생긴 수 / Python

2,3,5만을 약수로 가지는 합성수를 못생긴 수라고 한다

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

n번째 못생긴 수를 구하자

 

처음 아이디어 접근

 

일단 1,2,3,4,5가 못생긴 수인건 맞으니

dp = [1,1,1,1,1] 로 세팅한다

 

n이 5보다 작은 경우에는 n을 return하도록 한다

 

그 이상은 dp를 구한다

 

못생긴 수를 세는 cnt와 현재 수를 나타내는 cur 변수를 둔다

while문을 돌며 cnt가 n에 도달하면 멈춘다

 

while문 내에서 현재 살펴보는 수를 1씩 증가시킨다

현재 수가 2or3or5로 나누어떨어지고, dp[i//(2or3or5)-1]값이 1이라면

그 수는 2,3,5만을 인수로 가진다는 뜻

못생긴 수 cnt를 증가시키고, dp에도 못생긴 수라는 뜻으로 1을 삽입

 

그 외에는 0을 삽입한다

 

마지막에 현재 숫자를 return하면 n번째 못생긴 수를 알 수 있다

 

n = int(input())

if n<6:
    print(n)
else:
    dp=[1,1,1,1,1]
    cnt=5
    cur=5
    while cnt<n:
        cur+=1
        
        if (cur%2==0 and dp[cur//2-1]==1) or (cur%3==0 and dp[cur//3-1]==1) or (cur%5==0 and dp[cur//5-1]==1):
            dp.append(1)
            cnt+=1
        else:
            dp.append(0)
    print(cur)

 

 

답이 틀린건 아니지만

1000을 입력했을 때 출력에 오랜 시간이 걸렸다

 

while문 없이 for문으로도 구현이 되더라..

 

현재 못생긴 수에 대해 2,3,5를 곱하면 그역시 못생긴 수가 된다

 

1부터 n까지 for문을 돌며

가능한 곱셈 결과 중 가장 작은 수를 dp의 i번째 요소에 집어넣는다

i번째 요소에 집어넣어진 가장 작은 수가 무엇이 되었냐에 따라 2배,3배,5배 인덱스 중 하나를 증가시킨다

 

for문을 다 돈 후 n-1번째 dp 요소를 살펴보면 된다

 

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]*5
print(ugly[n-1])