[Python] 숫자 변환하기 - 프로그래머스 (DP)

해당 글은 프로그래머스 문제 '숫자 변환하기'를 다룬다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

 

설명

해당 문제는 DP문제로 간단하게 해결할 수 있다.

x에서 y까지 for문을 돌면서 dp 테이블을 최소값으로 유지하여 업데이트 시켜준다.

 

코드

def solution(x, y, n):
    answer = -1
    dp = [1000001]*1000001
    dp[x] = 0
    for i in range(x, y+1):
        if i+n <= y:
            dp[i+n]=min(dp[i+n], dp[i]+1)
        if i*2 <= y:
            dp[i*2]=min(dp[i*2], dp[i]+1)
        if i*3 <= y:
            dp[i*3]=min(dp[i*3], dp[i]+1)
            
    if dp[y] != 1000001:
        answer = dp[y]
    return answer