<그리디> 16953번 A → B with 파이썬

 

문제

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

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

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

입력

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

출력

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

정답비율

41.497%

알고리즘 분류

 #그리디 #그래프이론 #그래프탐색 #너비우선탐색

 

 

a, b = map(int, input().split())
result = 1
while a < b :
    if b % 2 == 0:
        b = b//2
        result += 1
    else :
        if str(b)[-1] == '1' :
            b = int(str(b)[:-1])
            result += 1
        else :
            break

if a == b :
    print(result)
else :
    print(-1)

 

 - 백준 알고리즘 분류를 보니 그래프를 이용해서 BFS로 풀 수도 있나보다. 하지만 필자는 단순 그리디문제로 풀었다.

 

 - 먼저 예제 1의 경우 2로 162를 만드는데 이를 역으로 생각하는 것이 편하다. 그 이유는 162에서 2를 만든다고 생각하면 2로 나누거나 끝에서 '1'을 빼는 연산이 되는데, 이는 선택지가 단 하나로 줄어든다는 말이기도 하다.

 

 - 다시 살펴보면 162에서 선택할 수 있는 방법은 2로 나누는 방법밖에 없다. 그 후 81에서 선택할 수 있는 방법은 당연히 끝에 '1' 을 빼는 방법 뿐이다. 따라서 B를 이용하여 2로 나누어 지면 2로 나누고, 그렇지 않으면 끝이 '1'이면 '1'을 빼고, '1'도 아니라면 만들 수 없는 경우이다.

 

 - result에 1씩 더해가도록 하였으며, a와 b가 다르다면 -1을 출력하도록 하였다.  

 

 

---

 

참고

 

16953번: A → B