백준 33707 (C++) 젓가락으로 메추리알 집기

최초 업로드: 2025-04-14 14:35:25

최근 수정 시간: 2025-07-25 09:53:18

게시자: rlatjwls3333

카테고리: 백준

# [Gold IV] 젓가락으로 메추리알 집기

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

## 문제 설명

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

세로로 $N$개, 가로로 $M$개의 정사각형 칸들로 이루어진 반찬통이 있다. 쿠가 메추리알을 거의 다 먹어 치워 버렸기에, 반찬통 안에는 메추리알이 단 한 칸에만 놓여 있다.

당신은 눈을 가린 채로, 반찬통 안의 어딘가에 남아 있는 메추리알 하나를 젓가락으로 집어먹어 보려 한다!

$N = 2, M = 3$일 때, 반찬통 안에 메추리알이 놓여 있는 모습이다.

당신은 $\left\lfloor \dfrac{NM}{2} \right\rfloor$번의 젓가락질 이내로 메추리알을 잡아야 한다. 젓가락질은 다음 과정으로 이루어진다.

<ul>
	<li>반찬통 안의 칸 하나를 골라 그 칸을 향해 젓가락질한다.</li>
	<li>젓가락질한 칸에 메추리알이 있다면, 메추리알을 집는다.</li>
	<li>젓가락질한 칸에 메추리알이 없다면, 메추리알은 다음 규칙에 따라 이동한다.
	<ul>
		<li>젓가락질한 칸이 메추리알이 있는 칸과 인접하다면, 메추리알은 인접한 무작위 칸 중 하나로 이동한다. 단, 방금 젓가락질한 칸이나 반찬통 밖으로는 이동하지 않는다.</li>
		<li>젓가락질한 칸이 메추리알이 있는 칸과 인접하지 않는다면, 메추리알은 이동하지 않는다.</li>
	</ul>
	</li>
</ul>

파란색 칸에 젓가락질하면 메추리알은 두 빨간색 칸 중 하나로 이동한다.

어떤 두 칸이 한 변을 공유하면 두 칸은 인접한다고 한다. 꼭짓점만을 공유하는 두 칸은 서로 인접하지 않는다.

정해진 젓가락질 횟수 안에 메추리알을 잡아보자!

## 입력

첫째 줄에 반찬통의 크기를 나타내는 정수 $N$, $M$이 공백으로 구분되어 주어진다. $left(2 le N, M le 100
ight)$

## 출력

당신은 표준 입출력으로 채점 시스템과 상호작용해야 한다. 다음과 같이 문자열을 한 줄에 출력하여 젓가락질할 수 있다.

<ul>
	<li><code>? r c</code>: 반찬통의 위에서 $r$번째, 왼쪽에서 $c$번째에 위치한 칸에 젓가락질한다. $(1 le r le N;$ $1 le c le M)$</li>
</ul>

당신은 최대 $\left\lfloor \dfrac{NM}{2} \right\rfloor$번 젓가락질할 수 있으며, 반찬통을 벗어나거나 횟수를 초과하는 경우 틀렸습니다를 받는다.

문자열을 출력한 이후, 당신은 젓가락질의 결과를 나타내는 정수 하나를 입력받아야 한다.

<ul>
	<li>메추리알을 집었다면 <code>1</code>을 입력받는다.</li>
	<li>메추리알을 집지 못했다면 <code>0</code>을 입력받고, 메추리알은 문제의 규칙에 따라 이동한다.</li>
</ul>

젓가락질의 결과로 <code>1</code>을 입력받았다면 프로그램을 즉시 종료해야 한다. 그렇지 않으면 예상하지 못한 채점 결과를 받을 수 있다.

각 행동을 출력한 이후, 프로그램은 매번 표준 출력을 flush해야 한다. 그렇지 않으면 시간 초과를 받을 수 있다. 대표적인 언어에서 표준 출력을 flush하는 방법은 다음과 같다.

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

이 문제의 인터랙터는 적응적이다. 메추리알의 시작 위치와 이동할 방향은 미리 정해져 있지 않다.

## 풀이
#### 최대 $\left\lfloor \dfrac{NM}{2} \right\rfloor$번 의 젓가락질을 할 수 있다는 것이 매우 큰 힌트이다. 반찬통을 체스판이라 생각을 하면 한 색을 순서대로 다 살펴보면 된다.

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

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

for(int i=0;i<n;i++) {
 for(int j=0;j<m;j++) {
 if(i%2!=j%2) {
 cout << "? " << i+1 << ' ' << j+1 << '\n' << flush;
 int res; cin >> res;
 if(res==1) return 0;
 }
 }
 }
}
```