[프로그래머스] Lv2. 숫자 변환하기(by Python)

문제

코딩테스트 연습 - 숫자 변환하기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

풀이

• 많이 나오는 유형의 DP문제이다.
• dp리스트를 최댓값으로 초기화하고, x에 3가지 옵션(n더하기, 2곱하기, 3곱하기)를 하면서 해당 dp값을 최솟값으로 갱신시켜주면 된다.

 

코드

def solution(x, y, n):
    answer = 0
    li = []
    dp = [1e9 for _ in range(y+1)]
    
    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] == 1e9:
        return -1
    else:
        return dp[y]