입출력 예시
x | y | n | result |
10 | 40 | 5 | 2 |
10 | 40 | 30 | 1 |
2 | 5 | 4 | -1 |
나의 코드
def solution(x, y, n):
answer = 0
q = []
q.append((y, 0))
while q:
num, cnt = q.pop(0)
if num == x:
return cnt
if num > x:
if num % 3 == 0:
q.append((num/3, cnt+1))
if num % 2 == 0:
q.append((num/2, cnt+1))
q.append((num-n, cnt+1))
return -1
Python
복사
•
DFS를 bottom up (x → y)으로 하면 모두 정수라서 경우의 수가 매우 많음 → 시간 오래 걸림. 대신 top down (y → x)로 하면 % 3, % 2를 하면서 정수가 아닌 경우가 많이 생기므로 시간을 절약할 수 있음.