[백준] 1463 (실버3)

해당 문제는 대표적인 다이나믹 프로그래밍 문제이다.

2를 1로 만드는 연산은 1을 빼는 것 혹은 2로 나누는 것, 총 1번이다.
3을 1로 만드는 연산은 우선 1을 빼서 2로 만든 후, 2를 1로 만드는 연산 1번을 더하는 것으로 총 2번이다. 하지만 3으로 나누는 연산이 더 효율적으로 작동하므로 총 1번의 연산으로 가능하다.
4를 1로 만드는 연산은 우선 1을 빼서 3으로 만든 후, 3을 1로 만드는 연산 1번을 더하는 것으로 총 2번이다.
즉, 이렇게 앞의 수의 연산 수를 저장한 후 활용하면 효과적으로 문제를 풀 수 있다는 것이다.

따라서 소스코드는 다음과 같다.

n = int(input())

d = [0] * (n + 1)

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