[백준] 16953번 - A -> B Python

Tuna·2022년 5월 16일
0

Greedy

목록 보기
13/22

문제


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

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

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

입력


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

출력


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

예제 입력 1


2 162

예제 출력 1


5

나머지 예제는 생략한다.

풀이


Python

import sys
input = sys.stdin.readline

a,b = map(int,input().rstrip().split())
answer= -1

def go(s,e,c):
    global answer
    if s == e:
        answer = c
        return 
    if s>e:
        return
    else:
        go(s*2,e,c+1)
        go(s*10+1,e,c+1)
    return

go(a,b,0)

if answer > 0 :
    print(answer+1)
else:
    print(answer)

정리


  • 백트래킹을 이용해 문제를 해결했다.
  • B보다 커지는 경우에는 더 탐색하지않고 return 시킨다.
  • BFSDP로도 문제를 해결할 수 있을 거 같은데 추후에 해봐야겠다.
profile
BE 개발자가 되기 위해 노력하는 사람

0개의 댓글