백준 1463

<정수를 1로 만들기>

난이도 : 실버 3

1. 백준 문제
   1463

2. 코드 알고리즘

• 동적계획법

점화식 구현해내는 게 관건인 동적계획법

• 1463

3. 코드

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

import sys
input = sys.stdin.readline

N = int(input())
D = [-1]*(N+1)
D[1] = 0

for i in range(2, N+1):
    D[i] = D[i-1] + 1
    if (i%2 == 0) : D[i] = min(D[i], D[i//2]+1)#1빼기 연산 그대로 or 나누기 연산이 더 작을 경우 교체
    #교체시 1 빼준만큼 더해야된다는 거 주의
    if (i % 3 == 0): D[i] = min(D[i], D[i//3] + 1)

print(D[N])