[BOJ 25907, 쉬움] 양과 늑대 (C++)

개인적인 난이도

쉬움

 

인터랙티브 문제가 처음이라면 https://www.acmicpc.net/problem/23306 이 문제를 먼저 풀어보길 바란다

인터랙티브 문제는 머리가 아프지만 실제 난이도에 비해 티어가 높게 잡히는 것 같기도 하고
풀어보면 재미있다. 개꿀임

---

성공한 풀이)

내가 컴퓨터고 컴퓨터가 사람이라고 생각한 뒤,

이분탐색을 이용해 컴퓨터랑 스무고개를 한다고 생각하면 된다

 

양의 숫자와 늑대의 숫자가 같아지기 위한 조건은, 어떤 짝수의 날짜 D에 대해

양의 숫자가 정확히 D/2만큼 존재하는 것이다. 우리는 그러한 날짜 D를 찾아내 ! D로 출력하면 된다.

양의 숫자가 D/2보다 많다면, 그 이후에 늑대와 양의 숫자가 같아지는 어떤 날이 존재할 것이다.
양의 숫자가 D/2보다 적다면, 그 이전에 늑대와 양의 숫자가 같아지는 어떤 날이 존재할 것이다.

이러한 논리를 바탕으로 아주 기본적인 이분탐색을 하면 답이 나온다

 

성공한 코드

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
using namespace std;

int main(void) {
	fastio;
	int N;cin>>N;
	int l=1,r=N,m;
	while (l+1<r)
	{
		int com;
		m = (l+r)/2;
		cout<<"? "<<m<<endl;
		cin>>com;
		if(m%2==0&&com==m/2){
			cout<<"! "<<m<<endl;
			return 0;
		}
		else if(com>m/2){//양이늑대보다많다
			l=m;
		}
		else{//늑대가양과같거나많다
			r=m;
		}
	}
	cout<<"! "<<l<<endl;
	return 0;
}