[백준] A → B(16953) - python

✏️ 문제

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

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

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

🎈 입력

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

🎈 출력

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

🎈 입출력 예

<입력>
2 162

<출력>
5
(2 → 4 → 8 → 81 → 162)

<입력>
4 42

<출력>
-1

<입력>
100 40021

<출력>
5
(100 → 200 → 2001 → 4002 → 40021)

👩‍💻 내 코드

처음에 풀 땐 구현해야 할 아이디어가 생각보다 쉽게 떠올라서 정답률이 40%가 맞는지 긴가민가 했다. 처음에 생각했던 방식은 아래와 같다.

• 맨 오른쪽에 1이 있는 경우 ➡️ 가장 오른쪽 1 제거 ➡️ 2로 나누기 ➡️ 반복
• 맨 오른쪽에 1이 없는 경우 ➡️ 2로 나누기 ➡️ 가장 오른쪽 1 제거 ➡️ 반복

그리고 아래와 같이 구현했더니 17%까지 가다가 바로 실패했다.ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

A, B = map(int, input().split())

count = 1
while A < B:
    if B%10 == 1:
        B = int(str(B).rstrip('1'))
        count += 1
    else:
        B //= 2
        count += 1

if A == B:
    print(count)
else:
    print(-1)
    

물론 쉽게 풀 수 있다는 생각은 전혀 없었다. 일단 테케부터 다 맞춰봐야겠다는 생각으로 짰는데 단호하게 바로 틀렸다고 해버리네..왜 틀렸는지 확인해보니 while의 조건문이 잘못된 것 같았다. 그리고 rstrip을 하지 않고 그냥 10을 나눈 몫으로 재할당 하면 될 것을 너무 어렵게 생각하고 있었다. 그래서 아래와 같이 수정하고 성공했다.

A, B = map(int, input().split())

count = 1
while A != B:
    tmp = B
    if B%10 == 1:
        B //= 10
        count += 1
    elif B%2 == 0:
        B //= 2
        count += 1
    if tmp == B:
        count = -1
        break

print(count)

내가 푼 방식은 그리디 알고리즘으로 top-down 방식인데, BFS를 이용해 bottom-up 방식으로 풀 수 있다고 한다. BFS로 푼 방식도 찾아보았는데 확실히 그리디가 조금 더 쉬운 방식인 것 같다. 이 곳에서 BFS 방식으로 푼 코드를 확인할 수 있다.