[BOJ_C++] 13777번 : Hunt The Rabbit

# 문제

• 1부터 50까지의 봉투 중 토끼가 들어있는 봉투를 알려준다.
• 봉투를 열어볼 땐 이분법을 사용한다. 따라서 맨 처음 열어보는 봉투는 항상 25가 된다.
• 이 때 열어보는 봉투를 모두 출력하라.

 

# 풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int low, high, mid;
    int key; cin >> key;
    while (key != 0) {
        low = 1, high = 50;
        while (low <= high) {
            mid = (low + high) / 2;
            cout << mid << " ";
            if (mid == key) break;
            if (mid < key) low = mid + 1;
            else high = mid - 1;
        }
        cout << "\n";
        cin >> key;
    }

    return 0;
}

• 입력받은 key가 0이라면 프로그램을 종료한다.
• 항상 봉투가 있는 범위는 1부터 50이기 때문에 low와 high를 1과 50으로 초기화 한다.
• low <= high인 동안 mid = (low + mid) / 2가 되고 이 값을 출력한다.
• mid가 key와 같다면 반복문을 탈출한다.
• mid가 key보다 작다면 key의 범위가 mid의 오른쪽이 되야한다. 따라서 low = mid + 1이 된다.
• mid가 key보다 크다면 key의 범위가 mid의 왼쪽이 되야하고 low = mid -1이 된다.
• 프로그램이 종료될 때 까지 반복한다.

 

# 결과