(파이썬)백준 알고리즘 1463번 1로 만들기

백준 알고리즘 저지 1463번 문제 (https://www.acmicpc.net/problem/1463)

 

 

1, 2, 3번 방법을 조합하여 1을 만드는 문제.

가장 적은 횟수를 찾는 문제인데 나는 1, 2, 3번 방법을 저장하고 중복을 제거하고, 그 결과에 대한 1, 2, 3을 수행하고 ... 1이 나오면 멈추도록함.

최적해의 시간 복잡도는 잘 모르겠지만 그에 비에 공간 복잡도가 안좋게 설계 된 코드일듯..

 

훗날 더 좋은 방법이 떠오르길

 

 
Q=[int(input())]
count=0
def doit(Qu):
    temp=[]
    for i in Qu:
        temp.append(i-1)
        if i%3==0:
            temp.append(i/3)
        if i%2==0:
            temp.append(i/2)
    temp=set(temp)
    temp=list(temp)
    return temp

while True:
    temp=Q[:]
    Q=[]
    Q=doit(temp)
    count+=1
    if min(Q)==1:
        break
print(count)