[프로그래머스] 숫자 변환하기 (파이썬)

문제 출처: 프로그래머스

프로그래머스

 

문제 설명

🔎 자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

- x에 n을 더합니다.
- x에 2를 곱합니다.
- x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

출처: 프로그래머스

---

아주 전형적인 DP문제였다. 그리고 어디서 풀어본 적도 있는 것 같은 문제였다.

 

<정답 코드>

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

    return DP[y] if DP[y] != float('inf') else -1

접근은 아래와 같다.

1. 정답을 저장할 DP배열을 만든다. (0부터 시작해도 되고 x부터 시작해도 된다. 편한대로)
2. n의 크기가 지정되어 있지 않으므로 x+n 또는 x*2 중 더 작은 수 부터 순회를 시작한다.
3. i의 크기에 따라 i-n, i//2 (2로 나누어 떨어진다면), i//3 (3으로 나누어 떨어진다면)의 DP 값 중 가장 작은 것 +1로 업데이트한다.

처음에 return 값에서 -1을 처리하지 않고 float 그대로 출력되게 놔두는 실수를 해서 valueError가 발생했었다.

 

끝까지 집중해서 다 풀자.