(Python/🥈2)백준리즘알고리즘 16953번: A>B

728x90

문제 바로가기

문제:

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

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

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

입력:

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

출력:

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

import sys
from collections import deque

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

A, B = map(int,input().split())
count = 1
def bfs(A,cnt):
    if A <= B:
        if A == B:
            print(cnt)
            exit()
        bfs(A * 2,cnt+1)
        bfs(int(str(A)+"1"),cnt+1)
    return -1
print(bfs(A,count))

내가 푼 방법은 바텀업 을 사용한 풀이이다. 하지만 탑 다운 방식이 더 좋을것 같다

조건 1. 2를 곱한다

조건 2. 뒤에 1을 붙인다.

붙이고 나면 cnt + 1을 해주고 다음 재귀에 넘기고 넘어간 값이 B와 같다면 출력해준다.

        if now * 2 <= b:
            q.append((now * 2, cnt + 1))
        if now * 10 + 1 <= b:
            q.append((now * 10 + 1, cnt + 1))
    print(-1)

이런식으로 bfs 를 사용해도 된다.