알고리즘 공부

1로 만들기
https://www.acmicpc.net/problem/1463
다이나믹 프로그래밍 문제
처음엔 그냥 1로 만들기만 하면 되는줄 알았더니 그 중에서 가장 적게 걸리는걸 찾는거였다!
되는거 다 넣고 젤 먼저 1 되는거 찾으면 된다!
다른 방법은 머리가 아프다

def solution(N):
    answer = int(0)
    dp = [N]
    while 1:
        if 1 in dp:
            return answer
        else:
            dp2 = []
            for i in dp:
                if i%3==0:
                    dp2.append(i/3)
                if i%2==0:
                    dp2.append(i/2)
                dp2.append(i-1)
            dp = dp2
            answer+=1
N = int(input())
print(solution(N))

소요시간 ; 45분