BJ_16953) [BFS] A → B

문제

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

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

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

입력

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

출력

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

---

나의 풀이

풀이1

[BFS]

# 10:42 ~ 11:28
A, B = map(int, input().split())
def multipy(x):
	  return x * 2
def append(x):
	  return int(str(x)+"1")

from collections import deque
q = deque([(A,1)])
r =-1
while q:
    num, cnt = q.popleft()
    if num == B:
        r = cnt
        break
    m = multipy(num)
    a = append(num)
    if m <= B:
        q.append((m,cnt+1))
    if a <= B:
        q.append((a,cnt+1))
print(r)

풀이2

[그리디]

조건들을 잘 나누는 것이 포인뚜!

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

특히 1이 추가된 숫자를 구하려면, 10으로 나누었을 때, 1이 나와야 한다.