[백준] 1463번(python 파이썬)

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

 

dp[] 리스트의 크기를 n+1개 만들고 10^6으로 초기화 한다.

 

dp[n] 부터 시작한다.

dp[10] : 시작 연산 횟수는 0으로 초기화

 

이제 갈수 있는 정수가 3가지 있다.

1. 3으로 나누어 떨어지면, 3으로 나눈값

2. 2로 나누어 떨어지면, 2로 나눈값

3. 1을 뺀값

 

10에서는 9, 5 로 갈 수 있다.

연산된 값에 있는 숫자와 (처음 나온 숫자면 10^6이 있을 것이고, 이전에 연산된 숫자면 연산 횟수가 있을 것이다)

이전 연산횟수 +1 중 작은 값을 저장한다.

 

x = int(input())

dp = [1e6] * (x + 1)
dp[x] = 0

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

make_one()
print(dp[1])