자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return
x를 y로 만들 수 없다면 -1을 return
제한사항
1 ≤ x ≤ y ≤ 1,000,000
1 ≤ n < y
"""
입출력 예시)
x = 10, y = 40, n = 5 -> 2
x = 10, y = 40, n = 30 -> 1
x = 2, y = 5, n = 4 -> -1
"""
## 의사코드 ##
# 최소 연산 횟수
# -> DP
# x+1부터 y까지 for문으로 순회
# x+n 과 x*2 중 더 작은 수부터 순회
# i에서 n을뺀 값, i가 2로 나누어 떨어지는 경우, i가 3으로 나누어 떨어지는 경우의 DP 값 중 가장 작은 것 + 1로 업데이트
통과한 코드
def solution(x, y, n):
dp = [float('inf')] * (y+1)
dp[x] = 0
# x+1부터 y까지 순회
for i in range(x+1, y+1):
# x+n 과 x*2 중 더 작은 수부터 순회
if i < x + n and i < x * 2:
continue
# i의 dp값과 i-n의 dp값 중 가장 작은 값 + 1로 업데이트
dp[i] = min(dp[i-n]+1, dp[i])
# i가 2로 나누어 떨어지는 경우
# i의 dp값과 i // 2의 dp값 중 가장 작은 값 + 1로 업데이트
if i % 2 == 0:
dp[i] = min(dp[i], dp[i//2]+1)
# i가 3으로 나누어 떨어지는 경우
# i의 dp값과 i // 3의 dp값 중 가장 작은 값 + 1로 업데이트
if i % 3 == 0:
dp[i] = min(dp[i], dp[i//3]+1)
return dp[y] if dp[y] != float('inf') else -1
