[백준] 14562번 태권왕 파이썬

문제

태균이는 지금 태권도 겨루기 중이다. 지금은 상대에게 지고 있지만 지금부터 진심으로 경기하여 빠르게 역전을 노리려 한다.

태균이가 현재 할 수 있는 연속 발차기는 두가지가 있다.

1. A는 현재 점수만큼 점수를 얻을 수 있는 엄청난 연속 발차기이다. 하지만 상대 역시 3점을 득점하는 위험이 있다.
2. B는 1점을 얻는 연속 발차기이다.

현재 태균이의 점수 S와 상대의 점수 T가 주어질 때, S와 T가 같아지는 최소 연속 발차기 횟수를 구하는 프로그램을 만드시오.

입력

첫째 줄에 테스트 케이스의 수 C(1 ≤ C ≤ 100)이 주어진다. 둘째 줄부터 C줄에 걸쳐 테스트 케이스별로 현재 점수 S와 T가 공백을 사이에 두고 주어진다. (1 ≤ S < T ≤ 100)

출력

각 줄마다 S와 T가 같아지는 최소 연속 발차기 횟수를 출력한다.

예제 입력 1

6
10 20
2 7
15 62
10 37
11 50
34 59

예제 출력 1

3
3
4
4
5
25

제출 답안

from collections import deque
import sys

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

c = int(input())
answer = []


def bfs(start, end):
    q = deque([(start, end, 0)])
    while q:
        start, end, cnt = q.popleft()
        if start == end:
            return cnt
        if start * 2 <= end + 3:
            q.append((start * 2, end + 3, cnt + 1))
        if start + 1 <= end:
            q.append((start + 1, end, cnt + 1))


for _ in range(c):
    s, t = map(int, input().split())
    answer.append(bfs(s, t))

print(*answer, sep="\n")