체스판에 비숍 배치하기¶
$N \times N$ 체스판에 $K$개의 비숍을 서로 공격하지 않도록 배치하는 방법의 수를 구하십시오.
알고리즘¶
이 문제는 동적 계획법을 사용하여 풀 수 있습니다.
체스판의 대각선에 다음과 같이 번호를 매깁시다: 검은색 대각선은 홀수 번호를, 흰색 대각선은 짝수 번호를 가지며, 대각선은 포함된 칸의 수가 감소하지 않는 순서로 번호가 매겨집니다. 다음은 $5 \times 5$ 체스판에 대한 예시입니다.
D[i][j]를 대각선 i와 같은 색이면서 번호가 i 이하인 대각선들에 j개의 비숍을 배치하는 방법의 수라고 합시다. 그러면 i = 1...2N-1이고 j = 0...K입니다.
D[i][j]는 D[i-2]의 값만을 사용하여 계산할 수 있습니다($i$와 같은 색의 대각선만 고려하므로 2를 뺍니다). D[i][j]를 얻는 방법은 두 가지입니다. 첫째는 j개의 비숍을 모두 이전 대각선들에 배치하는 경우로, 이렇게 하는 방법은 D[i-2][j]가지입니다. 둘째는 대각선 i에 비숍 하나를 배치하고 이전 대각선들에 j-1개의 비숍을 배치하는 경우입니다. 이렇게 하는 방법의 수는 대각선 i의 칸 수에서 j-1을 뺀 값과 같습니다. 이전 대각선들에 배치된 j-1개의 비숍 각각이 현재 대각선의 칸을 하나씩 막기 때문입니다. 대각선 i의 칸 수는 다음과 같이 계산할 수 있습니다:
int squares (int i) {
if (i & 1)
return i / 4 * 2 + 1;
else
return (i - 1) / 4 * 2 + 2;
}
기저 사례는 간단합니다: D[i][0] = 1, D[1][1] = 1입니다.
D[i][j]의 모든 값을 계산하고 나면, 답은 다음과 같이 구할 수 있습니다: 검은색 대각선에 배치되는 비숍의 가능한 모든 개수 i=0...K와, 그에 대응하는 흰색 대각선의 비숍 개수 K-i를 고려합니다. 검은색 대각선과 흰색 대각선에 배치된 비숍은 서로 공격하지 않으므로, 배치를 독립적으로 수행할 수 있습니다. 마지막 검은색 대각선의 번호는 2N-1이고, 마지막 흰색 대각선의 번호는 2N-2입니다. 각 i에 대해 D[2N-1][i] * D[2N-2][K-i]를 답에 더합니다.
구현¶
int bishop_placements(int N, int K)
{
if (K > 2 * N - 1)
return 0;
vector<vector<int>> D(N * 2, vector<int>(K + 1));
for (int i = 0; i < N * 2; ++i)
D[i][0] = 1;
D[1][1] = 1;
for (int i = 2; i < N * 2; ++i)
for (int j = 1; j <= K; ++j)
D[i][j] = D[i-2][j] + D[i-2][j-1] * (squares(i) - j + 1);
int ans = 0;
for (int i = 0; i <= K; ++i)
ans += D[N*2-1][i] * D[N*2-2][K-i];
return ans;
}