[프로그래머스] 154538. 숫자 변환하기 | DP | 파이썬, 소스코드, 정답

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

프로그래머스

---

문제 요약

x, y, n이 주어진다. 

+n, *2, *3연산으로 x를 y로 변환하여야 한다.

최소연산횟수를 구하라. (만약 x를 y로 변환할 수 없다면 -1)

---

문제 조건

• 1 <= x <= y <= 1,000,000
• 1 <= n < y

---

시행착오

전형적인 DP문제라고 생각했고 역시 DP로 풀 수 있었다.

근데 나머지 연산자 %와 몫 연산자 //를 헷갈려서 좀 헤맸다 ^^;; 바보

---

접근방법

• dp[i]는 x를 i로 변환하기위한 최소 연산 횟수이다.
• dp[i] = min(dp[i-n], dp[i//2], dp[i//3])+1이다.
• 단, i-n이 0보다 작은경우, i를 2로 나눌 수 없는 경우, i를 3으로 나눌 수 없는 경우에는 비교하지 않는다.

---

소스코드

def solution(x, y, n):
    dp = [-1]*(y+1)
    dp[x] = 0

    for i in range(x+1, y+1):
        if i-n >= 0 and dp[i-n] != -1:
            dp[i] = dp[i-n]+1

        if i % 2 == 0 and dp[int(i / 2)] != -1:
            dp[i] = (dp[i//2]+1) if dp[i] == -1 else min(dp[i], dp[i//2] + 1)

        if i % 3 == 0 and dp[int(i / 3)] != -1:
            dp[i] = (dp[i//3]+1) if dp[i] == -1 else min(dp[i], dp[i//3] + 1)

    return dp[y]