백준 1463번(python)

---

X = int(input())

dp = [X]
cnt = 0

while(True):
    if(1 in dp):
        print(cnt)
        break
    calc = []
    for i in dp:
        if(i % 2 == 0):
            calc.append(i / 2)
        if(i % 3 == 0):
            calc.append(i / 3)
        calc.append(i - 1)
    dp = calc

    cnt += 1

# 내가 푼건 dp방법이 아닌 것 같아 아래 코드를 붙임
# https://chunghyup.tistory.com/49 참고함
def min(x, y):
    return x if x <= y else y
 
x = int(input())
 
minimum_count = [0 for _ in range(x+1)]
 
index = 0
while(True):
    if index > x:
        break
 
    if index <= 1:
        minimum_count[index] = 0
    else:
        temp_min = x + 1
        if index % 3 == 0:
            temp_index = int(index/3)
            temp_min = min(temp_min, minimum_count[temp_index])
 
        if index % 2 == 0:
            temp_index = int(index/2)
            temp_min = min(temp_min, minimum_count[temp_index])
 
        temp_min = min(temp_min, minimum_count[index-1])
        minimum_count[index] = int(temp_min + 1)
    index = index + 1
    
print(minimum_count[x])

위의 코드는 0, 1 까지는 연산 횟수가 0이므로 일단 0을 채워준다.

미리 계산해놓은 인덱스(숫자 값)를 이용하여 최댓값을 구하는 방식.

점화식은 해당 리스트에서 min(/2, /3, -1) + 1이 된다. -> temp_min이 이 부분을 계산해주고 있음. 

마지막에 index = index + 1을 이용하여 점점 x값에 다가가게 됨.