백준 알고리즘 1463번 1로 만들기(python)

if X % 3 == 0: 
    X //= 3 
elif x % 2 == 0: 
    X //= 2 
else: 
    X -= 1~~~~

단순하게 위와 같은 방식으로 풀면 틀린다. 예를 들어 10 같은 경우 10 -> 5 -> 4 -> 2 -> 1 보다 빠른 

10 -> 9 -> 3 -> 1이 있기 때문이다.

2 또는 3으로 나누어 떨어지는 수더라도 그 수에 1을 빼준 값도 같이 다음 단계로 넘겨주는 식으로 해결했다.

X = int(input())
cnt = 0
li = [X]

while(1 not in li):
    t = []
    for x in li:
        if x % 3 == 0:
            t.append(x//3)
        elif x % 2 == 0:
            t.append(x//2)
        t.append(x-1)
    li = t
    cnt += 1
print(cnt)