[🥈1 / 백준 16953 / 파이썬] A → B

 

16953번: A → B

 

문제

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

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

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

출력

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

 

예제 입력 1  2 162	예제 출력 1  5
예제 입력 2  4 42	예제 출력 2  -1
예제 입력 3  100 40021	예제 출력 3  5

 

힌트

2 → 4 → 8 → 81 → 162

100 → 200 → 2001 → 4002 → 40021

 

풀이

 

bottom-up 대신 top-down으로 생각해야 한다.

a를 b로 만들지 않고, b를 a로 만들자.

 

일단 연산에 있어 속도적으로 우위를 점하는 것은 2를 나누는 것이 아닌 수의 끝의 1을 없애는 것이다.

따라서 b의 끝에 1이 존재한다면 b를 2로 나누기보단 끝의 1을 빼는 것이 최선이다.

 

그렇지 않다면 어쩔 수 없이 2로 나누는 연산을 해야 한다.

하지만, 홀수일 경우엔 2로 나눌 수 없으니 짝수인 경우에만 2로 나누도록 한다.

 

위 두 연산을 수행했지만 값의 변화가 없을 경우,

무한루프에 빠지게 된 것이므로 탈출하고 -1을 출력하면 된다.

 

a,b = map(int,input().split())
r = 1
while(b!=a):
    r+=1
    temp = b
    if b%10 == 1:
        b//=10
    elif b%2 == 0:
        b//=2
    
    if temp == b:
        print(-1)
        break
else:
    print(r)

 

한편 이 문제는 BFS로도 풀 수 있다.

BFS는 문제에 나온 정석대로 bottom-up으로 풀이한다.

 

BFS이니 큐를 준비한 뒤, a를 큐에 1과 함께 넣어준다.

1은 연산 횟수를 의미한다.

 

그리고 루프를 돌며 큐에 원소가 존재할 때 큐에서 pop한다.

pop한 원소가 b와 같다면, 멈춘 뒤 연산 횟수를 출력한다.

 

b보다 크다면, 다음 루프로 넘어간다.

 

b보다 작다면,

해당 원소에 2를 곱한 것과 끝에 1을 붙인 것 두 가지 경우를 큐에 넣어주도록 한다.

단, 연산 횟수에 +1을 하여 넣어주는 것을 잊으면 안 된다.

 

만약 큐에 원소가 모두 비었는데도 답을 출력하지 못했다면 -1을 출력한다.

 

from collections import deque
a,b = map(int,input().split())
q = deque()
q.append((a,1))
r = 0

while(q):
    n,t = q.popleft()
    if n > b:
        continue
    if n == b:
        print(t)
        break
    q.append((int(str(n)+"1"),t+1))
    q.append((n*2,t+1))
else:
    print(-1)