DOJ

해설

킹이 있는 칸을 $(r,c)$ 라고 하자. 위쪽 또는 아래쪽 변까지의 거리 중 작은 값을 $x$ , 왼쪽 또는 오른쪽 변까지의 거리 중 작은 값을 $y$ 라고 정의한다. 두 값을 각각 $3$ 에서 잘라낸 뒤 $x\le y$ 가 되도록 정렬한다.

킹의 현재 칸과 이동 가능한 칸은 킹을 중심으로 한 $3\times3$ 영역에만 존재한다. 이 영역의 칸을 공격하거나, 영역 안에 배치된 기물을 다른 기물로 보호하려면 킹에서 체비쇼프 거리 $3$ 보다 멀리 떨어진 나이트는 필요하지 않다. 비숍도 같은 대각선 위에서 더 가까운 위치로 옮겨 동일한 역할을 하도록 정규화할 수 있다. 따라서 경계까지의 거리가 $3$ 이상인 경우는 모두 동일하게 취급할 수 있다.

가능한 위치 유형은 다음 열 가지뿐이다.

(0,0),(0,1),(0,2),(0,3),(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)

각 유형에서 킹 주변의 유한한 영역만 조사하면 된다. 킹의 현재 칸과 이동 가능한 각 칸을 목표 칸으로 두고, 그 칸에 기물이 있다면 해당 기물을 제거한 상태에서 다른 기물이 목표 칸을 공격하는지 검사한다. 나이트의 공격은 곧바로 계산할 수 있고, 비숍은 목표 칸과 비숍 사이에 다른 기물이 없는지 확인한다.

$S=4,5,6$ 에서는 실제 체스판 전체를, $S\ge7$ 에서는 각 유형을 대표하는 $7\times7$ 판을 완전 탐색한다. 각 비숍 수에 대해 필요한 나이트 수의 최솟값을 구하면 다음 표를 얻는다. 표의 값 이하가 아니라, 주어진 나이트 수가 표의 값 이상일 때 가능하다. $B\ge5$ 인 열은 모두 $0$ 이다.

유형	$B=0$	$B=1$	$B=2$	$B=3$	$B=4$	$B\ge5$
$(0,0)$	$3$	$2$	$1$	$0$	$0$	$0$
$(0,1),(0,2),(0,3)$	$4$	$3$	$2$	$1$	$0$	$0$
$(1,1)$	$5$	$4$	$3$	$2$	$1$	$0$
나머지 유형	$5$	$4$	$2$	$1$	$0$	$0$

$S=2$ 에서는 어떤 위치도 불가능하다. $S=3$ 은 별도로 완전 탐색하며 다음 표를 사용한다. $\infty$ 는 불가능함을 뜻한다.

유형	$B=0$	$B=1$	$B=2$	$B=3$	$B=4$	$B=5$	$B\ge6$
$(0,0)$	$\infty$	$2$	$1$	$0$	$0$	$0$	$0$
$(0,1)$	$\infty$	$3$	$2$	$1$	$0$	$0$	$0$
$(1,1)$	$\infty$	$4$	$4$	$2$	$1$	$1$	$0$

이제 각 유형에 속하는 칸의 수를 센다. 한 좌표축에서 가장 가까운 경계까지의 거리를 $d$ 라고 할 때, 거리를 $3$ 에서 자른 값이 $d$ 인 좌표의 개수를 $C_d$ 라고 하자.

$d=0,1,2$ 에 대해서는 다음과 같다.

C_d=\begin{cases} 2 & (S\ge2d+2),\\ 1 & (S=2d+1),\\ 0 & (S\le2d). \end{cases}

그리고

C_3=\max(0,S-6)

이다.

유형 $(a,b)$ 에 속하는 칸의 수는 $a=b$ 이면 $C_aC_b$ , $a<b$ 이면 행과 열을 바꾸는 두 경우를 고려하여 $2C_aC_b$ 이다. 가능한 유형의 칸 수만 모두 더하면 정답이다.

완전 탐색으로 얻은 표는 각 유형과 정확한 기물 수에 대한 필요충분조건을 기록한다. 거리 분류에 의해 같은 유형의 칸은 동일한 국소 배치를 가지므로 같은 판정 결과를 갖는다. 마지막으로 위의 계수 공식은 모든 칸을 중복 없이 열 가지 유형 중 하나에 배정한다. 따라서 알고리즘이 더한 값은 가능한 킹 위치의 수와 정확히 같다.

시간 복잡도는 $O(1)$ 이고, 공간 복잡도도 $O(1)$ 이다. 정답은 최대 $S^2$ 이므로 64비트 정수형을 사용해야 한다.

Solution written by GPT5.6

비숍과 나이트

해설