[Python] 1463번 : 1로 만들기

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

---

12852번과 유사한 문제 

12852는 과정도 출력하는 부분이 추가되었다는 부분 말고는 같다

1을 빼는 경우

2로 나누는 경우 + 2로 나누었을때 카운트가 더 적을때

3으로 나누는 경우 + 3으로 나누었을때 카운트가 더 적을때

dp[i] 값을 갱신한다

 

n = int(input())
dp = [0]*(n+1)
for i in range(2,n+1):
    dp[i] = dp[i-1] + 1
    if i%3==0 and dp[i//3]+1 < dp[i]:
        dp[i] = dp[i//3]+1
    if i%2==0 and dp[i//2]+1 < dp[i]:
        dp[i] = dp[i//2]+1
print(dp[n])