[Programmers]Lv 2. 숫자 변환하기

문제:

풀이방법:

y를 만드는 것이 목적이므로 y 길이를 가지고 있는 DP 배열을 만들어서 연산을 수행하도록 한다.

DP에 연산을 하면서 연산 횟수를 채워나가면 되는데, 최소 연산 횟수를 구해야 하므로 min 연산을 추가로 하도록 한다. 즉, 특정 숫자 x에 접근할 수 있는 방법은 여러가지가 있을텐데 그 중 가장 작은 횟수만 선택하는 것이다.

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

문제링크:

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