c언어 33707번 젓가락으로 메추리알 집기 (백준)

#include <stdio.h>
int main() {
	int n,m,a,b,i,j;
	scanf("%d %d",&n,&m);
	b=(n*m)&1;
	for(i=1;i<=n;i++) {
		for(j=1+b;j<=m;j+=2) {
			printf("? %d %d\n",i,j);fflush(stdout);
			scanf("%d",&a);
			if(a)return 0;
		} b^=1;
	}
}

풀이 : 애드 혹

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

메추리알을 집지못하더라도 인접한 메추리알의 경우 주변으로 이동하는 성질을 이용하여, 위에서 아래로, 왼쪽에서 오른쪽으로만 집기를 시도해도, ⌊(n*m)/2⌋  만에 메추리알을 집는 것이 가능합니다.

 

1) n*m 이 짝수인 경우 : (1,1) 부터 시작합니다. +2 씩 오른쪽으로 이동하되, 영역을 침범하면 아래로 내려갑니다.

아래로 내려가선 (2,1)로 시작하는 것이 아닌 (2,2)로 시작합니다. 만약 3번째로 내려간다면 다시 (3,1)부터 시작하면 됩니다. ... 이를 반복합니다.

 

최대 10번만에 메추리알을 집을 수 있습니다.

 

 

 

 

2) n*m 이 홀수인 경우 : (1,2) 부터 시작해야 ⌊(n*m)/2⌋  만 에 집는것이 가능합니다. 이또한 +2씩 오른쪽으로 이동하며, 범영역을 침범하면 아래로 내려갑니다. (2,2)가 아니라 (2,1)로 시작합니다. 다시 내려가면 (3,2)로 시작합니다. ...이를 반복합니다.

 

 

최대 4번만에 메추리알을 집을 수 있습니다. 빨강 (1번), 주황(2번), 노랑(3번), 초록(4번)