[파이썬/python] 백준 14562 - 태권왕

문제

https://www.acmicpc.net/problem/14562

---

문제 설명

1.  경기에서 역전하기 위해 할 수 있는 연속 발차기의 종류는 두가지다.
   1. 발차기 A:  현재 점수의 2배가 된다. 하지만 상대도 3점을 득점한다.
   2. 발차기 B: 1점을 얻는다.
2. 태균이의 점수 S, 상대의 점수 T가 주어질 때 S == T가 되는 최소 연속 발차기 횟수를 구한다.

 

---

풀이

1차원 배열의 탐색 문제이다. 발차기를 했을 때 점수는 음수로 가지 않는다. 따라서 사이클이 존재하지 않고, 증가했을 경우만 확인하면 되기에 너비우선탐색(BFS)를 떠올렸다.

1. Queue에 나의 점수, 상대의 점수, 발차기 횟수를 입력한다.
   
   1. 계속해서 증가하기 때문에 방문처리는 따로 하지 않았다.
2. 발차기 A를 했을 때 결과를 queue에 입력한다.
   1. 발차기 A를 한 후 내 스코어가 상대 스코어보다 커진 경우 queue에 입력하지 않는다.
3. 발차기 B를 했을 때 결과를 queue에 입력한다.
   1. 발차기 B를 한 후 내 스코어가 상대 스코어보다 커진 경우 queue에 입력하지 않는다.
4. queue에서 꺼낸 현재 결과가 S == T라면 발차기 횟수를 반환한다.

---

코드

import sys
from collections import deque
input = sys.stdin.readline

C = int(input())
def bfs():

    while queue:
        my_score,score2,cnt = queue.popleft()
        if my_score == score2:
            return cnt
        if my_score*2 <= score2+3:
            queue.append((my_score*2, score2+3, cnt+1))
        if my_score+1 <= score2:
            queue.append((my_score+1,score2,cnt+1))

for tc in range(C):
    S,T = map(int,input().split())
    queue = deque()
    queue.append((S,T,0))
    print(bfs())

---

시간복잡도

• S와 T의 간격이 가장 클 때 시간복잡도가 최악일 것이다.
• $S == 1$이고 $T == 100$ 일 때
• 1에서 100까지 발차기 B를 했을 때 약 $O(T)$의 시간복잡도가 소요된다고 가정하자.
• 테스트 케이스 $C$개 만큼 반복하므로 약 $O(T*C) = O(100*100) = O(10^4)$의 시간복잡도가 소요된다.