Google Kick Start 2019. Number Guessing

Binary Search를 사용해 쉽게 구현할 수 있다.

변수가 알파벳 한 글자로 되어 있는데 (개인적으로 이런 변수 선언을 매우 싫어하지만 문제에 그렇게 나와있으니 그대로 진행...)

여러 번 반복 탐색을 통해 숫자 p가 무엇인지 맞추는 문제인데, t는 test case 개수, a와 b는 문제에서 제시하는 p의 minimum과 maximum, q는 나의 guessing이다.

 

Kick Start에는 흥미롭게도 interactive 형식의 문제가 있다. 이 문제가 바로 그런 형식인데, Kick Start의 judging system과 내가 짠 코드가 동시에 실행되는 것이다. 쉽게 말해서, 코드에서 출력한 값을 기반으로 다시 input을 받는 형식이다. 여기서는 내가 guess한 q값이 p와 일치하면 "CORRECT", 더 작으면 "TOO_SMALL", 더 크면 "TOO_BIG"을 입력받게 된다.

 

Guess한 값이 더 작을 경우에는 minimum을 q로 올려주고, 더 클 경우에는 maximum을 q로 내려주었다.

 

다음은 코드이다.

 

#include <iostream>
#include <string>
using namespace std;

int main() {

	int t, a, b, n, p, q;
	string word;
	cin >> t; //#testcase

	for (int i = 0; i < t; i++) {

		cin >> a >> b >> n; //exclusively lower bound, upper bound, and max number of guesses

		while (n >= 0) {

			q = (a + b) / 2;
			cout << q << '\n'; //my guess
			cin >> word;

			if (word == "CORRECT")
				break;
			else if (word == "TOO_SMALL") {
				a = q + 1;
				n--;
			}
			else { //TOO_BIG
				b = q - 1;
				n--;
			}
		}

	}

	return 0;
}