[백준 27650번] 마법박스 (C++)

https://www.acmicpc.net/problem/27650

27650번: 마법박스

 

인터렉티브 문제로 채점 방식이 특이하다.

"?"를 출력하여 문제에게 질문해야하고, 문제가 답을 주면 범위를 줄여서 물어보고... 그러다가 "!"로 답을 출력해야한다.

이 문제에서는 질문할 수 있는 횟수가 20번이므로 스무고개라고 생각하면 된다.

처음으로 이런 유형을 풀어봤고 문제랑 대화하는 느낌이 들어서 재밌었다.

---

 

마법박스에 들어있는 수 중에서 가장 작은 정수를 찾으면 되는데, 마법박스에 들어있는 수의 배수들이 무한히 박스에 들어있는 점이 특징이다. 좀만 생각해보면 소수와 관련있음을 알 수 있다.

예를 들어 4가 박스안에 없다고 가정하면, 당연히 배수를 해서 4가 되는 2도 박스안에 없다. 어차피 찾아야하는 수는 가장 작은 정수이므로 박스안에 없는 수 중에서 가장 작은 수들은 소수들만 남게 된다.

범위가 5,000,000 만 까지이므로 에라토스테네스로 걸러주고 남은 소수들로 매개 변수 탐색을 하면 끝.

 

#include <iostream>
#include <vector>
#define endl "\n"
using namespace std;

int n, q = 20, re, t;
int prime[5000001];
vector<int> v;

void net(){
	for(int i = 2; i*i <= n; i++){
		if(!prime[i]){
			for(int j = i*i; j <= n; j+=i){
				prime[j] = 1;
			}
		}
	}
	for(int i = 2; i <= n; i++){
		if(!prime[i]) v.push_back(i);
	}
}

int main() {
	cin >> n;
	t = n;
	net();
	
	int left = 0, right = v.size()-1;
	while(left <= right && q > 0){
		int mid = (left+right)/2;
		cout << "? " << v[mid] << endl;
		cout << flush;
		cin >> re;
		if(re){
			left = mid + 1;
		} else{
			right = mid - 1;
			t = v[mid];
		}
		q--;
	}
	cout << "! " << t << endl;
	cout << flush;
}