[알고리즘 문제풀이] 1로 만들기

문제 제목 : 1로 만들기

문제 난이도 : 하

문제 유형 : 동적 프로그래밍, 다이나믹 프로그래밍

https://www.acmicpc.net/problem/1463
시간 제한 : 0.15초
메모리 제한 : 128MB

문제풀이 아이디어

< 소스코드 >

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

for i in range(2,x+1): # 2부터 x까지 반복
    dp[i]=dp[i-1]+1 # 1을 빼는 연산 -> 1회 진행
    if i%2==0: # 2로 나누어 떨어질 때, 2로 나누는 연산
        dp[i]=min(dp[i],dp[i//2]+1)
    if i%3==0: # 3으로 나누어 떨어질 때, 3으로 나누는 연산
        dp[i]=min(dp[i],dp[i//3]+1)
print(dp[x])