SWE(4839)_이진탐색

작성일 | In

SWE 4839 이진탐색

책의 전체 쪽수와 두 사람이 찾을 쪽 번호가 주어졌을 때, 이진 탐색 게임에서 이긴 사람이 누구인지 알아내어 출력

이진탐색 게임이란 ? 이진 탐색만으로 지정된 페이지를 먼저 펼치는 사람이 이기는 게임 ex) 책이 400쪽이라고 가정해보자. a는 300, b는 50을 찾아야 하는 경우를 생각해보자

아이디어

이것저것 해보다가 결국 시간이 너무 지나고 머리가 안돌아가서 코드를 봤다. 안보고 다시 써보는 연습을 해보자. 이진탐색 정도는 외워도 괜찮겠다.

코드

TC = int(input())

for tc in range(1, TC + 1):
    info = list(map(int, input().split()))

    result = []
    for j in range(2):
        start = 1
        end = info[0]
        page = info[j+1]
        cnt = 0

        while start <= end:
            mid = (start + end) // 2
            if mid == page:
                break
            elif mid < page:
                start = mid
                cnt += 1
            else:
                end = mid
                cnt += 1

        result.append(cnt)

    if result[0] < result[1]:
        print('#%s' % tc, 'A')
    elif result[0] == result[1]:
        print('#%s' % tc, 0)
    else:
        print('#%s' % tc, 'B')

참고자료

[참고한 블로그]https://tothefullest08.github.io/algorithm/2019/03/05/7_4839_%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89/

0%