백준 1463 - 1로 만들기 [python/파이썬]

num = int(input())
 
 
def get_min(num):
    dp = [[] for _ in range(num+1)]
    dp[0] = [num]
    for i in range(num):
        for step in dp[i]:
            if step == 1:
                return i
            if step % 3 == 0:
                dp[i + 1].append(step // 3)
            if step % 2 == 0:
                dp[i + 1].append(step // 2)
            dp[i + 1].append(step - 1)
 
 
print(get_min(num))

다이내믹 프로그래밍으로 코드를 작성했지만 이중 for문이라 다른 정답자들에 비해 효율적이지 못하다...