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

-코드

n = int(input())
arr = [0, 0, 1, 1]
for i in range(4, n + 1):
    arr.append(arr[i - 1] + 1)
    if i % 2 == 0:
        arr[i] = min(arr[i], arr[i // 2] + 1)
    if i % 3 == 0:
        arr[i] = min(arr[i], arr[i // 3] + 1)

print(arr[n])

다이나믹 프로그래밍이 부족해서 가닥을 잡기 위해 풀어본 문제로 피보나치의 수는 식을 찾아서 바로 풀 수 있었지만 이것은 수식을 내가 찾아야 해서 도저히 몰라서 질문 게시판 등 찾아보고 해서 풀긴 했으나 가닥만 잡고 좀 더 많이 풀어봐야 할 것 같다.