[BOJ] 1463 1로 만들기 (python)

백준 1463. 1로 만들기 (파이썬)

 

1463번: 1로 만들기

import sys

X = int(sys.stdin.readline())
L = [0] * (X + 1)

for i in range(2, X + 1):
    if i % 2 == 0 and i % 3 == 0:
        L[i] = min(L[i - 1] + 1, L[i // 2] + 1, L[i // 3] + 1)
    elif i % 2 == 0:
        L[i] = min(L[i - 1] + 1, L[i // 2] + 1)
    elif i % 3 == 0:
        L[i] = min(L[i - 1] + 1, L[i // 3] + 1)
    else:
        L[i] = L[i - 1] + 1

print(L[X])

 

1부터 시작해서 정해진 수까지 최단 거리로 올라간다는 느낌

2로 나누는 경우와 3으로 나누는 경우 중에서도 최소값을 찾는 게 중요했다