<aside> 🔥 백준 13777번 문제

</aside>

<aside> 🔥 문제 정리

1번 ~ 50번까지의 봉투가 있고, 이 중 한개의 봉투에 토끼 그림이 들어있다.

이진 탐색을 통해 토끼의 그림을 찾을 때 열어본 봉투의 번호를 알아내야한다.

입력값으로 토끼의 그림이 들어있는 봉투의 번호가 주어진다.

0이 입력되면 종료한다.

출력값으로는 해당 봉투를 찾을 때까지 열어본 봉투의 번호를 출력한다.

# 입력
25
17
31
0

# 출력
25
25 12 18 15 16 17
25 38 31

</aside>

<aside> 🔥 접근 방법

이 문제는 그냥 이진 탐색을 해서 mid값을 출력하면 되는 문제인 것 같다.

31번에 토끼가 있을 경우 예시

Untitled

</aside>

<aside> 🔥 코드

  1. 입력값으로 target을 받아주고 1부터 50번까지의 봉투 리스트를 생성하고 이진탐색을 시작한다.

    while True:
    target = int(input())
    if target == 0:         # 0 입력 시 종료
        break

    # 1부터 50까지 봉투 만듬
    nums = [i for i in range(1, 50 + 1)]

    # 결과값
    ans = []

    # 이진 탐색 시작
    binary_search(0, len(nums) - 1)

  2. 이진 탐색

    재귀적으로 호출될 때마다 중간지점을 결과값에 추가한다.

    def binary_search(left, right):
    if left <= right:
        # 중간 지점.
        mid = left + (right - left) // 2
        # 중간 지점을 값에 추가.
        ans.append(mid+1)

        # 좌 우로 탐색.
        if nums[mid] < target:
            return binary_search(mid + 1, right)
        elif nums[mid] > target:
            return binary_search(left, mid - 1)
        else :
            return mid

  3. 결과값 출력

    print(' '.join(list(map(str, ans))))

Untitled

</aside>