[백준/파이썬/그래프] 25418번 정수 a를 k로 만들기 코딩테스트 연습풀이

문제 출처: https://www.acmicpc.net/problem/25418

25418번: 정수 a를 k로 만들기

 

문제

입력으로 양의 정수 A와 K가 주어지면, 아래 연산을 이용하여 A를 K로 변경하려고 한다. 정수 A를 변경할 때 사용할 수 있는 연산 종류는 다음과 같다.

• 연산 1: 정수 A에 1을 더한다.
• 연산 2: 정수 A에 2를 곱한다.

정수 A를 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력하자.

 

입력

첫 번째 줄에 양의 정수 A와 K가 빈칸을 사이에 두고 순서대로 주어진다.

 

출력

첫 번째 줄에 양의 정수 A를 양의 정수 K로 만들기 위해 필요한 최소 연산 횟수를 출력한다.

 

정답

a, k = map(int, input().split())
cnt = 0
while 1:
    if a == k:
        print(cnt)
        break
    if k % 2 == 0 and k >= a*2:
        k = int(k/2)
    else:
        k-=1
    cnt+=1

bfs로 구현했다가 시간초과돼서 계산하는 방식으로 바꿔서 정답