https://www.acmicpc.net/problem/1463

x = int(input())

d = [0] * (x+1)

for i in range(2, x+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[x])

시행착오

처음 이 문제를 보자마자 '3으로 나누어 떨어지면 나누기 -> 2로 나누어 떨어지면 나누기 -> 1빼기' 와 같이 문제를 풀려고 했다. 당연히 오답이였고 문제 힌트에 테스트케이스 10을 보고 잘못 풀었다는 걸 알았다. 어떻게 풀어야 할까 생각을 하던 중에 알고리즘 분류에 다이나믹 프로그래밍이 있는 걸 보고 이전의 답들로 정답을 구할 수 있겠다는 생각이 들었다. 예를 들어 10을 구할 때는 9의 값(2)에 +1, 9를 구할 때는 3의 값(1)에 +1 와 같이 d[i] = min(d[i//3] + 1, d[i//2] + 1, d[i-1] + 1)점화식이 세워진다는 걸 알았다.

알게된 점

구하고자 하는 문제의 작은 정답들이 반복되고 언제나 그 값이 똑같다면 점화식을 세워보자. 작은 정답들 간에 규칙과 구조를 파악하고 문제를 풀어볼 것