Bishop and Knight

킹이 있는 칸을 $(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$이다.

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

이제 각 유형에 속하는 칸의 수를 센다. 한 좌표축에서 가장 가까운 경계까지의 거리를 $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