백준 1463 1로 만들기 (Python,Pypy)

#1463 1로 만들기
import sys
import math

input = sys.stdin.readline
N = int(input())

#0,1,2,3으로부터 최단거리로 1을 만드는 방법#
dp = [0,0,1,1]
for x in range (4,N+1):
    if x % 2 != 0 and x % 3 != 0:
        y = dp[x-1] + 1
        dp.append(y)
    elif x % 2 != 0 and x % 3 == 0:
        y = min(dp[x//3],dp[x-1]) + 1
        dp.append(y)
    elif x % 2 == 0 and x % 3 != 0:
        y = min(dp[x//2],dp[x-1]) + 1
        dp.append(y)
    else:
        y = min(dp[x//2],dp[x//3],dp[x-1]) + 1
        dp.append(y)

print(dp[N])