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

문제 설명

자연수 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

---

내 코드

def solution(x, y, n):
    answer = 0
    dp = set()
    dp.add(x)
    
    while dp:
        if y in dp:
            return answer
        else:
            dp_y = set()
            for i in dp:
                if i+n <= y:
                    dp_y.add(i+n)
                if i*2 <= y:
                    dp_y.add(i*2)
                if i*3 <= y:
                    dp_y.add(i*3)
            dp = dp_y
            answer += 1
            
    return -1

아이디어

dp를 활용한 문제였다.
x를 y로 변환하기 위한 최소 연산의 수가 필요하기 때문에 set 을 활용했다.

1. x 값을 dp에 우선 대입한다.
2. y 가 dp에 있다면, 정답을 리턴
3. dp를 돌면서, i+n i*2 i*3 3가지 연산 중 y보다 작거나 같으면 dp_y라는 set에 add한다.
4. 3번 연산을 마친 dp_y에 dp를 copy하면서 (answer+1)하면서 1~3 과정을 반복한다.