[1463] 1로 만들기 in python

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

17626번: Four Squares

> dp

 

i%2로 나눠지고 i%3으로 나눠지면

min함수를 이용해서 

어떤 경우를 선택해야 최솟값으로 나오는 지 

확인해야한다.

 

위에서 구한 값과

-1을 뺀 값중에서도

어떤 경우를 선택해야 최솟값으로 나오는 지

확인해야 한다.

 

 

import sys

n = int(sys.stdin.readline())
dp = [0 for _ in range(n + 1)]
dp[0], dp[1] = 0, 0
for i in range(2, n + 1):
    temp=1e9
    if i % 2 == 0:
        temp= min(temp, dp[i // 2] + 1)
    if i % 3 == 0:
        temp = min(temp, dp[i // 3] + 1)
    dp[i] = min(temp, dp[i - 1] + 1)
print(dp[n])