[프로그래머스/Python] Lv 2. 숫자 변환하기

⭐ 문제 링크

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

프로그래머스

 

 

⭐ 풀이 코드

# dp 알고리즘

# 현재까지 도달하는 데 연산 수 + 1 과 도달하려고하는 수에 저장된 값을 비교하여, 
# 작은 값을 현재 연산 수로 저장

def solution(x, y, n):
    answer = 0
    
    d = [1e9] * (y+1) # 큰 수로 초기화
    d[x] = 0
    
    for i in range(x, y+1):
        
        # n을 더하는 경우
        if i+n <= y:
            d[i+n] = min(d[i+n], d[i]+1)
        
        # 2를 곱하는 경우
        if i*2 <= y:
            d[i*2] = min(d[i*2], d[i]+1)
        
        # 3을 곱하는 경우
        if i*3 <= y:
            d[i*3] = min(d[i*3], d[i]+1)
        
    if d[y] == 1e9:
        return -1
    
    return d[y]