SWEA 4839 이진탐색 (python)

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

 

[파이썬 S/W 문제해결 기본] 2일차

2021.04.21 - [Algorithm] - SWEA 4836 색칠하기 (python)

2021.04.19 - [Algorithm] - SWEA 4837 부분집합의 합 (python)

2021.04.21 - [Algorithm] - SWEA 4839 이진탐색 (python)

2021.04.21 - [Algorithm] - SWEA 4843 특별한 정렬 (python)

 

 

유사문제

2021.04.21 - [분류 전체보기] - SWEA 5207 이진탐색 (python)

 

문제

코딩반 학생들에게 이진 탐색을 설명하던 선생님은 이진탐색을 연습할 수 있는 게임을 시켜 보기로 했다.

짝을 이룬 A, B 두 사람에게 교과서에서 각자 찾을 쪽 번호를 알려주면, 이진 탐색만으로 지정된 페이지를 먼저 펼치는 사람이 이기는 게임이다.

예를 들어 책이 총 400쪽이면, 검색 구간의 왼쪽 l=1, 오른쪽 r=400이 되고, 중간 페이지 c= int((l+r)/2)로 계산한다.

찾는 쪽 번호가 c와 같아지면 탐색을 끝낸다.

A는 300, B는 50 쪽을 찾아야 하는 경우, 다음처럼 중간 페이지를 기준으로 왼쪽 또는 오른 쪽 영역의 중간 페이지를 다시 찾아가면 된다.

	A	B
첫 번째 탐색	l=1, r=400, c=200	l=1, r=400, c=200
두 번째 탐색	l=200, r=400, c=300	l=1, r=200, c=100
세 번째 탐색		l=1, r=100, c=50

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

[입력]

첫 줄에 테스트 케이스 개수 T가 주어진다. 1<=T<=50

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

[출력]

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

코드

import sys
sys.stdin = open("input.txt")

T = int(input())

def binary_search(info):
    #  정보 불러오기
    P = info[0]
    Pa = info[1]
    Pb = info[2]

    # 현재 위치한 페이지
    now = 0
    # 왼쪽페이지와 오른쪽 페이지 초기값
    L = 1
    R = P

    # A와 B의 횟수
    count_A = 0
    count_B = 0

    # Pa 검사
    while not now == Pa:
        # 중앙값
        center = int((L+R)/2)
        # 중앙값이 어디에 위치하냐에 따라 범위 바꿔줌
        if Pa > center:
            L = center
        else :
            R = center
        # 현재위치 설정
        now = center
        # 횟수 증가
        count_A += 1

    # 현재 위치한 페이지
    now = 0
    # 왼쪽페이지와 오른쪽 페이지 초기값
    L = 1
    R = P

    # Pb 검사
    while not now == Pb:
        # 중앙값
        center = int((L + R) / 2)
        # 중앙값이 어디에 위치하냐에 따라 범위 바꿔줌
        if Pb > center:
            L = center
        else:
            R = center
        # 현재위치 설정
        now = center
        # 횟수 증가
        count_B += 1

    if count_A < count_B:
        return 'A'
    elif count_A > count_B:
        return 'B'
    else:
        return 0



for tc in range(1, T+1):
    info = list(map(int, input().split()))
    result = binary_search(info)
    print("#{} {}".format(tc,result ))