숫자 변환하기

⭐️
def solution(x, y, n):

    maxSize = 1000001
    dp = [maxSize for i in range(maxSize)]
    dp[x] = 0

    # DP 응용
    for i in range(x,y+1):
        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] == maxSize:
        return -1

    return dp[y]

• 조건을 복잡하게 달기에도 로직이 너무 꼬이고, dfs/bfs로 구현하기에도 복잡하다.
• DP를 응용해서 해결한다.
  - 어느 값에 도달하는 최소 횟수를 구하는 것이기 때문에 계산한 값과 배열에 저장된 값을 비교해서 더 작은 값으로 바꾸고
  - 이를 계속 반복해서 수행하면 DP[y]에 y로 변환하기 위한 최소 횟수가 저장된다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges