[CLASS 4]백준 16953번 - A → B

16953번 : A → B

 

이전에 이 문제와 비슷한 문제를 푼 적이 있었는데, 그 문제가 더 어려웠던 것 같다. 이 문제는 일단 수가 무조건 증가하기 떄문에 해당 수를 넘기면 그 수에 대해서는 검사하지 않아도 된다.

 

내 코드:

# dawitblog.tistory.com
from collections import deque

a,b = map(int,input().split())
queue = deque([(a,0)])

while queue:
    temp,count = queue.popleft()
    n = temp * 2
    m = temp * 10 + 1

    if n == b or m == b:
        print(count+2)
        exit()
    if n < b:
        queue.append((n,count+1))
    if m < b:
        queue.append((m,count+1))

print(-1)

 

bfs를 통해 간단하게 구현할 수 있다. 그런데 사실 이 문제는 bfs를 사용하지 않아도 된다...

 

skyhp님의 코드:

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

 

그냥 m에서 거꾸로 내려오는 방식을 사용해도 된다!!