Dynamic Programming(DP) - 1로 만들기[1463]

조건

• X가 3으로 나누어 떨어지면, 3으로 나눈다.
• X가 2로 나누어 떨어지면, 2로 나눈다.
• 1을 뺀다.

Idea

DP (Bottom-Up 방식) : 결과 저장용 리스트인 DP 테이블을 통해 1부터 N까지 순차적으로 1을 만들기 위한 최소 연산 횟수를 저장

 

# 여기서 만든 로직은 제일 작은 수인 1부터 순차적으로 최소 연산 횟수로 1을 만드는 방법을 저장하면서 N까지 도달하는 것 
N = int(input())
dp = [0] * (N+1)

# 1은 아무런 연산을 하지 않아도 되므로, 2부터 시작
for i in range(2, N+1):
    
    # +1 = 일단 -1 연산을 했을때의 경우를 카운팅한 것
    dp[i] = dp[i-1]+1
    
    # -1 연산을 한 경우와 3 으로 나누는 경우 중에서 횟수가 더 적은 것을 택함
    # -1 or //3 연산을 한 경우와 2로 나누는 경우 중에서 횟수가 더 적은 것을 택함
    if i%3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)
        
    if i%2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
        
print(dp[N])