백준 #1463 <1로 만들기>

난이도 : 실버3
소요시간 : 31m
사용한 풀이법 : DP

---

풀이 과정

1. dp용 리스트 선언 후 0으로 초기화
   1. dp 리스트는 인덱스 숫자가 1이 되기까지의 최소연산횟수를 저장하는 용도
2. 2~n+1까지 루프 실행
   1. dp[i] = dp[i-1]+1 : i번째 수는 i-1번째 수의 dp값에 +1을 한것을 디폴트로 둔다
   2. 만일 i가 2나 3으로 나누어 떨어진다면, i에 2를 나눈 몫의 수에 해당하는 dp값과 디폴트값을 비교하여 최소값을 선택한다

 

작성 코드

n=int(input())
dp = [0]*(n+1)

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

print(dp[n])