백준 16953번: A->B Python 풀이 및 정답 코드

문제 링크

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

16953번: A → B

 

 

문제 설명

문제

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

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

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

입력

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

출력

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

 

 

문제 풀이

최소니까 bfs 이용하는게 더 좋으려나? 했는데 만들 수 없는 경우도 알아내야 하므로 끝까지 가봐야하는건 매한가지다.

그래서 그냥 dfs로 풀었다.
재귀 좋아

 

 

코드

A, B = map(int, input().split())
counts = []

def dfs(current, count):
    if current == B:
        counts.append(count)
        return
    elif current > B:
        return
    else:
        dfs(current*10 + 1, count+1)
        dfs(current*2, count+1)

dfs(A, 1)

if counts:
    print(min(counts))
else:
    print(-1)

 

 

결과

 

 

 

다른 사람의 코드

 

 

 

리뷰

그나저나 슬슬 백준도 깃에 정리할 때가 된 것 같다...