[SWEA 4839].[파이썬 S/W 문제해결 기본] 2일차 - 이진탐색

SW Expert Academy에서 학습용으로 문제를 가져왔습니다. 문제가 될 시 수정, 삭제하겠습니다.

https://swexpertacademy.com/main/main.do

문제 : 
코딩반 학생들에게 이진 탐색을 설명하던 선생님은 이진탐색을 연습할 수 있는 게임을 시켜 보기로 했다.
짝을 이룬 A, B 두 사람에게 교과서에서 각자 찾을 쪽 번호를 알려주면, 이진 탐색만으로 지정된 페이지를 먼저 펼치는 사람이 이기는 게임이다.
예를 들어 책이 총 400쪽이면, 검색 구간의 왼쪽 l=1, 오른쪽 r=400이 되고, 중간 페이지 c= int((l+r)/2)로 계산한다.
찾는 쪽 번호가 c와 같아지면 탐색을 끝낸다.
A는 300, B는 50 쪽을 찾아야 하는 경우, 다음처럼 중간 페이지를 기준으로 왼쪽 또는 오른 쪽 영역의 중간 페이지를 다시 찾아가면 된다.

책의 전체 쪽수와 두 사람이 찾을 쪽 번호가 주어졌을 때, 이진 탐색 게임에서 이긴 사람이 누구인지 알아내 출력하시오. 비긴 경우는 0을 출력한다.

[입력]

첫 줄에 테스트 케이스 개수 T가 주어진다.  1<=T<=50
테스트 케이스 별로 책의 전체 쪽 수 P, A, B가 찾을 쪽 번호 Pa, Pb가 차례로 주어진다. 1<= P, Pa, Pb <=1000

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, A, B, 0 중 하나를 출력한다.

input

3
400 300 350
1000 299 578
1000 222 888

output

#1 A
#2 0
#3 A

code

def binary_search(start, end, target, count):
    m=(start+end)//2
    if m==target:
        return count
    if target > m:
        return binary_search(m,end,target,count+1)
    else:
        return binary_search(start,m,target,count+1)


Test_case=int(input())

for t in range(1,Test_case+1):
    P, A, B =map(int,input().split())
    count_A=binary_search(1,P,A,0)
    count_B=binary_search(1,P,B,0)
    if count_A>count_B:
        print("#{} B".format(t))
    elif count_A == count_B:
        print("#{} 0".format(t))
    else:
        print("#{} A".format(t))

binary_search함수를 정의해주는데 만약 중간값((시작과 끝)/2=중간값)이 원하는 타겟값과 같아지면 count를 0으로 하고 만약 중간값이 target보다 작다면 처음값으로 중간값을 넣고 count에 1을 더해주고 다시 계산합니다.
또한 만약 target보다 중간값이 크다면 끝값으로 중간값을 넣고 count에 1을 더해주고 다시 이진분류를 시작합니다.
그 후 count값이 높은것이 더 오래걸린것이므로 count가 적은 값을 이겼다고 출력해줍니다.