[알고리즘][Python] 백준(BOJ) 16953 A → B_파이썬

 

16953 A → B    www.acmicpc.net/problem/16953

16953번: A → B

 

 

 

문제 풀기 전 공부할 것 : 그래프 탐색, 너비 우선 탐색

 

 

 

 

 

 

 

풀이 1

<내용>

• bfs를 이용해서 해결한다.
• que에 (a, 1)을 넣는다.
• popleft를 통해 뽑은 숫자에서 가능한 연산을 한다.
  • 만약 2를 곱했을 때 b보다 크다면 que에 넣지 않는다.
  • 만약 1을 수의 가장 오른쪽에 추가했을 때 정수가 b보다 크면 que에 넣지 않는다.

 

 

<코드>

from collections import deque

a, b = map(int, input().split())
res = -1
que = deque([(a, 1)])
while que:
    i, cnt = que.popleft()
    if i == b:
        res = cnt
        break
        
    if i*2 <= b:
        que.append((i*2, cnt+1))
    if int(str(i)+'1') <= b:
        que.append((int(str(i)+'1'), cnt+1))

print(res)

 

 

 

 

 

 

 

 

풀이 2

<내용>

• 위의 과정과 다르게 b에서 a를 만들어 해결한다.
• while문을 통해 과정을 반복한다.
  • 만약 a == b면 while문을 break 한다.
  • 만약 b가 2로 나누어 떨어지지 않으며 b의 마지막 자리의 숫자가 1이 아니거나 b가 a보다 작다면 b에서 a를 만들 수 없는 경우(a에서 b를 만들 수 없는 경우)이므로 -1을 출력한다.
  • 만약 b의 마지막 자리의 숫자가 1이면 b에서 1을 제거한다.
  • 만약 b가 2로 나누어 떨어지면 2로 나눈다.

 

 

<코드>

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