백준 27865 (C++) 랜덤 게임?

최초 업로드: 2025-09-21 08:24:36

최근 수정 시간: 2025-09-21 08:26:29

게시자: rlatjwls3333

카테고리: 백준

# [Bronze I] 랜덤 게임?

[문제 링크](https://www.acmicpc.net/problem/27865)

## 문제 설명

이 문제는 인터랙티브 문제이다.

처음에 인터랙터는 $1$부터 $N$까지 정수 중에서 균등한 확률로 수를 하나를 뽑는다. 질문을 통해 인터랙터가 현재 가지고 있는 수를 맞추면 이 문제를 맞힐 수 있다.

당신은 다음과 같은 질문을 최대 $20\,000$번 할 수 있다.

만약 질문의 답이 '아니오.'라면 인터랙터는 현재 가지고 있는 수를 버리고 새로 수를 뽑는다.

## 입력

양의 정수 $N$이 주어진다. $(1 \le N \le 1\,000)$

## 출력

다음을 표준 출력 스트림(stdout)으로 한 줄에 출력하여, 인터랙터가 가지고 있는 수가 무엇인지 질문할 수 있다.

<ul>
	<li><code>? x</code> : 현재 인터랙터가 가지고 있는 수가 $x$인지 확인한다. $(1\le x\le N)$</li>
</ul>

질문을 한 뒤, 당신은 인터랙터에게서 문자 하나를 입력받아서 질문의 답을 알 수 있다.

<ul>
	<li><code>Y</code> : 현재 인터랙터가 가지고 있는 수는 $x$와 같다.</li>
	<li><code>N</code> : 현재 인터랙터가 가지고 있는 수는 $x$와 다르다. 이후 인터랙터는 현재 가지고 있는 수를 버리고 새로 수를 뽑는다. 수를 뽑을 때는 질문의 답을 참고하지 않고 $1$부터 $N$까지 정수 중에서 균등한 확률로 수를 하나를 뽑는다.</li>
</ul>

질문을 한 후에는 반드시 표준 출력 버퍼를 flush 해야 하고, 표준 입력 스트림(stdin)을 통해 질문에 대한 답을 입력받아야 한다. 그렇지 않으면, 시간 초과 또는 런타임 에러를 받는다. 범위를 벗어난 $x$값을 질문하거나 잘못된 형식으로 질문하면 틀렸습니다를 받는다. 또한 $20\,000$회 넘게 질문을 하면 틀렸습니다를 받는다.

만약 인터랙터가 현재 가지고 있는 수를 알아낸 경우, 표준 출력 스트림으로 다음 한 줄을 출력한다.

<ul>
	<li><code>! y</code> : 현재 인터랙터가 가지고 있는 수는 $y$이다.</li>
</ul>

답을 출력한 이후에는 표준 출력 버퍼를 비우고 프로그램을 바로 종료하여야 한다. 그렇지 않으면 예상하지 못한 채점 결과를 받을 수 있다.

각 언어별로 표준 출력 버퍼를 flush하는 방법은 다음과 같다.

<ul>
	<li>C: <code>fflush(stdout)</code></li>
	<li>C++: <code>std::cout << std::flush</code></li>
	<li>Java: <code>System.out.flush()</code></li>
	<li>Python: <code>sys.stdout.flush()</code></li>
</ul>

## 풀이
모든 수가 1과 다를 확률은 최대 $0.999^{20000}$ 입니다. 1번이 맞다고 대답할 때까지 계속 물어보면 됩니다. 만약 틀린다면 한번 로또를 사보는 것을 추천 드립니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;

while(true) {
 cout << "? 1\n" << flush;
 char input; cin >> input;
 if(input=='Y') {
 cout << "! 1\n" << flush;
 return 0;
 }
 }
}
```