python/Q-35 at main · Whisoo0817/python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#실행속도 차이
#next2,next3,next5=2,3,5 (min최소 집어넣고)->4,3,5(min최소 집어넣고)->4,6,5->8,6,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.      #i2,i3,i5는 1,2,3,4,5,6,...
        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])


'''n=int(input())
dp=[0,1]
def solution(a):
    if a>1000:
        return
    a*=2
    if a not in dp and a<1000:
        dp.append(a)
    solution(a)
    a=int(a/2)
    a*=3
    if a not in dp and a<1000:
        dp.append(a)
    solution(a)
    a=int(a/3)
    a *= 5
    if a not in dp and a<1000:
        dp.append(a)
    solution(a)
    a=int(a/5)
solution(1)
dp.sort()
print(dp[n])'''