t_1로만들기_217

문제

4가지 연산이 주어 졌을때 연산을 최소화해서 1을 만들고자함
연산횟수 구하세용

답

이게 다이나믹프로그래밍로 풀어라는 방법이 안주어졌다면 햇갈렷을 것 같다. 그리디로 하면 틀린다.
ans이라는 이전 계산 스탭들을 저장하는 배열을 만들어서 활용했다.

from collections import deque

n = int(input.strip())

arr = deque([n])
ans = [-1] * (n+1)
ans[n] = 0

def cal(v, step):
    if v % 5 == 0:
        arr.append(v//5)
        ans[v//5]=step+1
    if v % 3 == 0:
        arr.append(v//3)
        ans[v//3]=step+1
    if v % 2 == 0:
        arr.append(v//2)
        ans[v//2]=step+1
    arr.append(v-1)
    ans[v-1]=step+1
    
while ans[1] < 0 and len(arr)>0:
    tmp = arr.popleft()
    cal(tmp,ans[tmp])

print(ans[1])