백준 21869 (C++) Maximum Bishop

최초 업로드: 2025-10-30 05:01:28

최근 수정 시간: 2025-10-30 05:01:28

게시자: rlatjwls3333

카테고리: 백준

# [Silver II] Maximum Bishop

[문제 링크](https://www.acmicpc.net/problem/21869)

## 문제 설명

체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. 다음 그림과 같은 $5\times5$ 정사각형 체스판 위의 B라고 표시된 곳에 비숍이 있을 때, 비숍은 대각선 방향으로 움직여 X로 표시된 칸에 있는 다른 말을 잡을 수 있다.

$N$-Maximum Bishop 문제는 $N \times N$ 체스판 위에 최대한 많은 비숍을 서로 공격할 수 없도록 배치하는 문제다.

$N$이 주어졌을 때, 최대한 많은 비숍을 서로 공격할 수 없도록 배치해보자.

## 입력

첫째 줄에 N이 주어진다. ($1 \leq N \leq 524\,288$)

## 출력

배치할 수 있는 비숍의 최대 개수 $M$을 첫 번째 줄에 출력한다. 이후 $M$개의 줄에 걸쳐 비숍을 배치해야 하는 행의 번호와 열의 번호를 공백으로 구분해서 출력한다. 행과 열의 번호는 $1$부터 시작한다.

답이 여러 개인 경우에는 그중 아무거나 출력한다.

## 풀이
n=1인 경우를 제외하고, 맨 윗줄과 맨 아랫줄에 n-1개씩 배치할 수 있다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 if(n==1) {
 cout << "1\n1 1";
 } else {
 cout << 2*(n-1) << '\n';
 for(int i=1;i<=n-1;i++) cout << "1 " << i << '\n' << n << ' ' << i << '\n';
 }
}
```