[BOJ] 16953번. A->B

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

2를 곱한다.
1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

예제 입력

2 162

예제 출력

5

풀이 1

첫번째로 생각했던 풀이는 m에서부터 n을 역추적하는 방식이다. 끝이 1로 끝나면 앞의 값을 m에 넣고, 2로 나누어 떨어지면 2로 나눈 값을 m에 넣었다.

코드 1

n,m=map(int, input().split())
count=0
while True:
  if m==n:
    break
  elif m%10==1:
    m=m//10
  elif m%2==0 and m!=0:
    m=m//2
  else:
    count=-2
    break
  count+=1
print(count+1)

풀이 2

사실 이 문제를 푼 목적이 bfs를 연습하기 위함이라, bfs를 사용해서 또 풀었다.

코드 2

from collections import deque

n,m=map(int, input().split())
s=n
queue=deque([(1,n)]) # 1,n 튜플을 deque로 변환
while queue:
  count, x=queue.popleft()
  if x==m:
    print(count)
    break
  if x*2<=m:
    queue.append((count+1,x*2))
  if x*10+1<=m:
    queue.append((count+1, x*10+1))
else:
  print(-1)

기억할 것

파이썬에서는 while-else, for-else문을 통해 반복문이 조건에 의해 정상종료(break, continue 사용 X) 되었음을 판별할 수 있다. 반복문이 정상종료했을 경우에는 아래의 else문이 실행된다.