[백준] 태권왕🦿

태권왕

문제설명

❓문제

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

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

• A는 현재 점수만큼 점수를 얻을 수 있는 엄청난 연속 발차기이다. 하지만 상대 역시 3점을 득점하는 위험이 있다.
• 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

➰문제접근방식

• ✔들어오는 순서대로 나가는 형식의 deque를 선언해준다.

• ✔q라는 변수에 내점수를 의미하는 S, 상대방 점수인 T, 그리고 발차기를 할때마다 1씩 추가할 수 있는 count변수 안에 대입해준다. 그리고 입력받은 q의 값들을 hit,hurt,cnt라는 변수에 넣어준다.

• ✔내 점수가 상대방의 점수 보다 낮을 동안 2가지의 발차기를 시도하면서, 내 점수와 상대방 점수 같아졌을때 발차기 횟수를 return해준다.

• ✔몇 번의 케이스가 있는지 C라는 변수에 담아주고 그 수만큼 반복문을 돌아준다

• ✔입력받은 함수를 split을 통해 각각 S랑 T라는 변수에 담아주고 bfs함수를 실행해준다.

➰코드

from collections import deque 

def bfs(S, T):
    q = deque()
    q.append((S, T, 0))
    while q:
        hit, hurt, cnt = q.popleft()
        #내가때린게 맞은거보다 더 작을동안
        if hit <= hurt  :
            # 내가 맞은거 *2, 타격+3 발차기횟수 + 1
            q.append((hit*2, hurt+3, cnt+1))
            # 내가 맞은거 +1, 발차기횟수 + 1
            q.append((hit+1, hurt, cnt+1))

            # 점수가 동일해졌을경우 몇 번 발차기를 했는지 cnt값을 return
            if hit == hurt:
                return cnt

C = int(input())
for _ in range(C):
    S,T = map(int, input().split())
    print(bfs(S,T))