백준 16953번 A → B

정보

문제 바로가기 [클릭]

난이도: Silver1

관련 개념: #그래프 이론 #그리디 알고리즘 #그래프 탐색 #너비 우선 탐색

---

조건

시간 제한	메모리 제한
2 초	512 MB

---

문제

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

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

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

---

입력

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

---

출력

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

---

예제 입출력 1

입력

2 162

출력

5

2 → 4 → 8 → 81 → 162

---

예제 입출력 2

입력

4 42

출력

-1

---

예제 입출력 3

입력

100 40021

출력

5

100 → 200 → 2001 → 4002 → 40021

---

코드(파이썬)

a, b = map(int, input().split())
cnt = 1
result = -1

while ((b%10 == 1) or (b%2 == 0)) and b > 0:
    if a == b:
        result = cnt
        break
    
    b //= 2 if b%2 == 0 else 10
    
    cnt += 1

if a == b:
    result = cnt
    
print(result)

---

특이사항

• b에서부터 거꾸로 출발하는 경우, 선택지가 1개로 고정되어 보다 단순한 풀이 가능

---

참고문헌

-