[알고리즘/백준] 1463번 : 1로 만들기(python)

리스트 대신 딕셔너리를 사용해서 값을 찾는 연산 속도를 줄일 수 있다.

def solution(N):
    x = [0 for _ in range(N + 1)]

    for i in range(2, N + 1):
        x[i] = x[i-1] + 1
        if i % 3 == 0:
            x[i] = min(x[i], x[i // 3] + 1)
        if i % 2 == 0:
            x[i] = min(x[i], x[i // 2] + 1)
    print(x[N])


if __name__ == "__main__":
    solution(int(input()))