[프로그래머스 - lv2] 숫자 변환하기 / 파이썬

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

---

문제 풀이)

다이나믹프로그래밍의 바텀업 방식을 이용해 풀었다.

x, y가 100,0000 범위의 문제라 단순 구현으로 풀었어도 해결했을거라 생각했었지만 자연스럽게 DP로 풀어야 된다는 느낌을 받았다.

맨처음 직관적으로 떠오른 점화식은 다음과 같았다,

 

x를 x를 구하기 위한 최소 연산 횟수라고 가정하면 이전항과 다음항들의 관계는 다음과 같을 것이다,

 

DP[x]  = min(DP[x - n] + 1, DP[x // 2] + 1, DP[x // 3] + 1, DP[x])

 

자 그렇다면 y까지의 index를 갖는 DP 테이블의 값을 INF 값으로 초기화 시켜준다.

그 다음 문제에서 준 argument x의 값을 0으로 초기화 시키면 된다. 즉, DP[x] = 0 이다.

이후 각각 n을 뺀값, 2로 나눈값, 3으로 나눈값과 현재 인덱스의 값에서 최솟값을 비교해가며 DP 테이블을 업데이트 시키면 문제를 해결할 수 있다.

 

import sys
def solution(x, y, n):
    answer = 0
    dp = [sys.maxsize] * (y + 1)
    dp[x] = 0
    for i in range(x, y+1):
        dp[i] = min(dp[i-n] + 1, dp[i])
        if i % 2 == 0:
            dp[i] = min(dp[i // 2] + 1, dp[i])
        if i % 3 == 0:
            dp[i] = min(dp[i // 3] + 1, dp[i])
    return dp[y] if dp[y] != sys.maxsize else -1