[백준] 16953 A -> B python

문제

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

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

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

입력

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

출력

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

코드 1

A,B = map(int,input().split())
cnt = 1
while True:
    if B==A:
        break
    if (B%2!=0 and B%10!=1) or B<A:
        cnt=-1
        break
    else:
        if B%10==1:
            B=B//10
            cnt += 1
        else:
            B=B//2
            cnt+=1
print(cnt)

풀이 1

 B->A

B가 A가 될 때까지 2로 나누거나 1의 자릿수가 1이면 1을 없애준다.

A를 못 만들면 -1 return!!

---

코드 2

from collections import deque

A,B = map(int,input().split())
res = -1
q = deque()
q.append([A,1])

while q:
    n,cnt = q.popleft()
    if n==B:
        res = cnt
        break
    if n*2<=B:
        q.append([n*2,cnt+1])
    if int(str(n)+"1")<=B:
        q.append([int(str(n)+"1"),cnt+1])
print(res)

풀이 2

 A->B : BFS 사용

BFS을 사용하는 방법이 있다. 이는 풀이 1을 풀고 다른 풀이들을 보고 깨달았다.................(코린이 ㅋㅋ)

 

1) 큐에 A와 연산 횟수를 삽입한다.

2) A가 B가 되기 위한 연산을 하여 큐에 대입한다.

3) B일 때 끝낸다.