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

다이나믹 프로그래밍의 기본 문제다.

핵심은 "한번만 연산" 한다는 것이다. 탐색이나 bf 로도 풀 수 있겠지만 문제 특성상 반복되는 부분이 많고

이러한 반복되는 부분을 중복 계산 하지 않기 위해서 다이나믹 프로그래밍을 한다.

 

cnt리스트에 100000을 붙인 이유는 나누기3 나누기2 마이너스1 중에서 해당사항이 없는 요소는

min에 값이 포함시키지 않기 위해서이다.

 

너무 오랜만에 파이썬으로 풀어서 문법이 헷갈릴 정도였다. 시험도 끝났으니 앞으로 매일 1~2문제씩은

꾸준히 열심히 푸는것을 목표로 해야겠다. 

num = int(input())
cnt = [100000] + [0 for i in range(num)]
for i in range(2,num+1):
    div3 = 0
    div2 = 0
    if i % 3 == 0:
        div3 = int(i / 3)

    if i % 2 == 0:
        div2 = int(i / 2)

    minus = i-1
    answer = min(cnt[div3],cnt[div2],cnt[i-1]) + 1
    cnt[i] = answer
print(cnt[-1])