숫자 변환하기

숫자 변환하기

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

---

풀이

dp

def solution(x, y, n):
    if x == y:
        return 0

    dp = [float('inf')] * (y + 1)
    dp[x] = 0
    #초기화 작업
    #dp 리스트를 생성하고 모든 요소를 양의 무한대(infinity)로 초기화
    #특정 인덱스(x 인덱스)의 요소만 0으로 초기화
    #float('inf'): 파이썬에서 무한대를 나타내는 특별한 값
    print(dp)
    for i in range(x, y + 1):
        if dp[i] == float('inf'):
            continue

        if i + n <= y:
            dp[i + n] = min(dp[i + n], dp[i] + 1)

        if i * 2 <= y:
            dp[i * 2] = min(dp[i * 2], dp[i] + 1)

        if i * 3 <= y:
            dp[i * 3] = min(dp[i * 3], dp[i] + 1)

    if dp[y] == float('inf'): # 만들 수 없을 때 
        return -1
    print(dp)
    return dp[y]
    

def solution(x, y, n):
  answer = 0
  s = set()
  s.add(x)

  while s:
      if y in s: # 같으면 
          return answer

      nxt = set() # 초기화 
      for i in s:
          print(i)
          if i+n <= y:
              nxt.add(i+n)
          if i*2 <= y:
              nxt.add(i*2)
          if i*3 <= y:
              nxt.add(i*3)
          print(nxt)
 
      s = nxt
      print("s", s)
      answer+=1

  return -1