프로그래머스 / DP / 숫자 변환하기

문제

---

 

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

프로그래머스

 

입출력

---

 

 

해설

---

 

x에서 y로 변환할 때 필요한 최소 연산 횟수를 구하는 문제이다.

 

해당 문제에서는 아래와 같은 3가지 연산이 가능하다.

1. x에 n을 더한다.
2. x에 2를 곱한다
3. x에 3을 곱한다

해당 연산들은 각각 1씩 가중치를 가진다.

 

DP를 통한 풀이가 가능하며 DP 테이블은 다음과 같이 정의한다.

DP[i] := i를 만들 때 필요한 최소 연산 횟수

 

DP테이블은 위에 연산을 통해서 채워나가면 된다.

 

정답코드

---

'''
'25. 10. 17.(금)

1. x -> y 변환

1. x + n
2. x << 1
3. x * 3

1 <= x <= y <= 10^6
1 <= n < y

DP로
DP[i] := i로 변환하기 위해 필요한 최소 연산 횟수

테이블 정의
'''
def solution(x, y, n):
    MAX = 0x3f3f3f3f
    dp = [MAX] * (y + 1)    
    dp[x] = 0#base
    
    for i in range(x, y + 1):
        if i - n >= 0 and dp[i - n] != MAX:
            dp[i] = dp[i - n] + 1
        
        if i % 2 == 0 and dp[i >> 1] != MAX:
            dp[i] = min(dp[i], dp[i >> 1] + 1)
        
        if i % 3 == 0 and dp[i // 3] != MAX:
            dp[i] = min(dp[i], dp[i // 3] + 1)
    return [dp[y], -1][dp[y] == MAX]

 

깃허브 : https://buly.kr/Nkfiq5

유튜브 : https://youtu.be/L8UelYZ5fdM