백준 1463 : 1로 만들기 (DP)

앞 포스트인 설탕배달과 같은 문제를 만나면 Greedy 성격을 띄는지 우선 확인해야한다.
https://velog.io/@yhy258/%EB%B0%B1%EC%A4%80-2839-%EC%84%A4%ED%83%95%EB%B0%B0%EB%8B%AC-DP

3, 4, 5와 같은 input이 들어오면

• 3으로 나눠지는가 ? -> 나눠지면 나누기.
• 2로 나눠지는가 ? -> 나눠지면 나누기.
• 다 안되면 1 빼기

이 방법이 통한다. 하지만 10이 들어오면 (10 - 1) / 3 / 3이 최적의 답이다. (greedy하지 않다.)
그럼 동적계획법을 잘 활용해서 풀어보자.

Memoization을 위해 필요한 크기만큼 list를 만들어주고 수행한다.

# 1. Greedy 한 성격을 띄는가? 10 -> 10 - 1 / 3 (dp로 풀자.)
# Bottom up; 경우를 모두 고려.
"""
    N = 1 -> 0
    N = 2 -> 1
    N = 3 -> 1
    N = 4 -> 2
    N = 5 -> 3
    ...
    
    d[N] = d[N-1] + 1
    if N % 3 == 0 :
        min(d[N//3] + 1, d[N]) # 나눴을 때랑 그냥 뺐을때 뭐가 더 작은가?
    if N % 2 == 0 :
    ... 이런식으로
"""

N = int(input())

memory = [0] * (N+1)
memory[1] = 0

def f(N):
    for i in range(2, N+1):
        memory[i] = memory[i-1] + 1
        if i % 3 == 0 : # 3 우선 고려.
            memory[i] = min(memory[i], memory[i//3] + 1)

        if i % 2 == 0 :
            memory[i] = min(memory[i], memory[i//2] + 1)

f(N)
print(memory[N])