[프로그래머스][Lv. 2] 숫자 변환하기

📁문제 설명

자연수 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
    s = set()
    s.add(x)
    
    while s:
        if y in s:
            return answer
        
        s2 = set()
        for i in s:
            if i*2 <= y:
                s2.add(i*2)
            if i*3 <= y:
                s2.add(i*3)
            if i+n <= y:
                s2.add(i+n)
                
        s = s2
        answer += 1
        
    return -1

dq(분활정복)을 이용한 문제다. 아직 알고리즘에 대해 하나도 모르는 것 같다... 더 열심히 공부해서 혼자 힘으로 풀 수 있도록 노력해야겠다!