체스판의 크기를 나타내는 정수 N이 입력으로 주어집니다. 이 문제의 목표는 임의의 N 값에 대해 N×N 체스판 위에 서로 공격할 수 없도록 비숍을 최대 몇 개까지 배치할 수 있는지 구하는 것입니다. 비숍은 대각선 방향으로 이동하며 공격하기 때문에, 두 비숍이 같은 대각선 상에 위치하면 안 됩니다.
예제
입력 − N = 2
출력 − 2×2 체스판에 배치 가능한 최대 비숍 수 − 2 (위 그림 참조)
설명 − 위 그림에서 보듯이 두 비숍이 서로 공격하지 않는 유일한 배치가 표시된 위치이며, 2×2 체스판에서는 최대 2개까지만 배치할 수 있습니다.
입력 − N = 5
출력 − 5×5 체스판에 배치 가능한 최대 비숍 수 − 8 (위 그림 참조)
접근 방법
N×N 체스판에 배치할 수 있는 최대 비숍의 개수는 간단한 수식으로 계산할 수 있습니다. N이 2 이상일 때 정답은 항상 2 × (N−1)입니다. 그 이유는 다음과 같습니다.
- 비숍은 같은 행이나 열에 있어서는 서로 공격하지 못하고, 오직 대각선으로만 공격합니다.
- 따라서 체스판의 맨 윗줄과 맨 아랫줄 전체에 비숍을 놓으면 같은 줄 안에서는 충돌이 발생하지 않습니다.
- 다만 네 모서리에 있는 비숍들은 반대편 모서리의 비숍과 대각선으로 마주 보게 되므로, 한쪽 줄의 양 끝 모서리 두 개를 제외하면 총 2N − 2개, 즉 2 × (N−1)개가 됩니다.
이제 프로그램에서 사용한 접근 방식을 단계별로 살펴보겠습니다.
- 체스판의 크기로 정수 N을 입력받습니다.
- N을 totalBishops(int n) 함수의 인자로 전달합니다.
- N < 1이면 잘못된 입력이므로 비숍 수는 0입니다.
- N = 1이면 배치할 수 있는 칸이 하나뿐이므로 비숍 수는 1입니다.
- 그 외의 경우에는 비숍 수를 2 × (N−1)로 계산합니다.
- 결과를 변수 bishops에 저장한 뒤 반환합니다.
예제 코드
#include <iostream>
// 배치 가능한 최대 비숍 수를 반환하는 함수
int totalBishops(int n){
int bishops = 0;
if (n < 1)
bishops = 0;
else if (n == 1)
bishops = 1;
else
bishops = 2 * (n - 1);
return bishops;
}
int main(){
int N = 15; // 체스판 크기 N*N
printf("%d", totalBishops(N));
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
28
N = 15인 경우 2 × (15 − 1) = 28이므로, 15×15 체스판에는 최대 28개의 비숍을 서로 공격하지 않게 배치할 수 있습니다. 이처럼 단순한 수식 하나만으로 O(1) 시간 복잡도에 문제를 해결할 수 있습니다.