[백준] 16953번 A → B - 그리디알고리즘 파이썬

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

16953번: A → B

 

문제 접근 방법

순방향을 A->B라고 한다면 역방향으로 풀면 쉽게 풀 수 있다. 기본적으로 2를 계속 나누고 끝자리가 1이면 1을 제거해 준다. 하지만 종료 조건을 잘 생각해봐야한다.

 

첫 제출코드

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

이렇게 했지만 계속 오류가 났다. 알고 보니 종료 조건에서 B<A만 -1로 업데이트 하는 로직밖에 없어서 55와 같은 숫자를 처리하지 못했다. 

 

최종 제출코드

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

(B % 2 !=0 and B % 10 !=1) 이렇게 조건을 추가하여 -1이 출력되는 조건을 보완해서 성공했다.

그리고 서칭을 해보니 BFS로 푸는 방법이 공유되어 있어 공부해보았다.

 

결과