[백준 16953번] (A -> B) - 파이썬

 

문제 링크:

https://www.acmicpc.net/problem/16953

16953번: A → B

 

풀이 과정:

A를 B로 바꾸려고 하지 말고, 역으로 B를 A로 바꾸는 방법을 생각해보자. 이를 적용해도 필요한 연산의 횟수는 같다.

우선순위 정하기 -

1을 수의 오른쪽에서 제거하는 것이, 2로 나누는 것보다 연산을 더 빠르게 할 수 있다.

while문, if문을 활용하여 그리디 알고리즘으로 최적의 해를 도출해보자.

 

풀이 코드:

# 16953번 A -> B

a, b = map(int, input().split())
count = 1

while True:

  if a == b:
    break
  elif (b% 2 != 0 and b% 10 != 1) or (b < a):
    count = -1
    break
  else:
    if b % 10 == 1:
      count += 1
      b //= 10
    else:
      count += 1
      b //= 2
  
print(count)

 

이 문제는 BFS로도 문제를 풀 수 있다. 아직 BFS에 대한 개념이 부족하기에, 추후 공부한 후 다시 올려보도록 하겠다.

16953번 A->B 파이썬