[프로그래머스] 숫자 변환하기 (Python) - dp

문제 설명

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

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

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

---

제한사항

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

---

입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

---

입출력 예 설명

입출력 예 #1
x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #2
x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

 

입출력 예 #3
x를 y로 변환할 수 없기 때문에 -1을 return합니다.

---

def solution(x, y, n):
    #같은 경우 처리
    if x==y:
        return 0
    
    #다른 경우 처리 - dp
    ns = [x+n, x*2, x*3]
    answer = [-1 if i not in ns else 1 for i in range(y+1)]
    
    for i in range(x, y+1):
        n1 = answer[i-n] + 1 if i-n > 0 and answer[i-n] > 0 else answer[i]
        n2 = answer[i//2] + 1 if i%2 == 0 and i//2 > 0 and answer[i//2] > 0 else answer[i]
        n3 = answer[i//3] + 1 if i%3 == 0 and i//3 > 0 and answer[i//3] > 0 else answer[i]
        ns = [n for n in [n1, n2, n3, answer[i]] if n > 0]
        answer[i] = min(ns) if len(ns) > 0 else answer[i]
    return answer[y]

딱 봐도 DP 같은 문제였다!

찬찬~히 x 부터 y 까지 올라가면서, 최소 몇 번의 연산이 필요한지 계산했다

초기에 x+n, x*2, x*3에 1을 집어넣는 것을 깜빡해서 한번 틀리고 ...

그리고 조건을 만족하지 않으면 answer[i] 그대로 가도록 해야하는데 거기에 -1 넣어서 한번 틀리고...

마지막에 answer[i] 갱신해줄 때, 현재 있는 값과도 비교해야 하는데 까먹어서 한번 틀렸다 ㅎ

 

오늘 하루종일 풀었던 문제가 있었는데...

도저히 이해가 안돼서 그냥 포기하고 푼 문제 ㅎㅎ ... ;) (심한 욕)

에효효!!!!!