문제
N×N 체스판에 서로 공격하지 못하도록 비숍을 최대 몇 개 놓을 수 있는지 구하라.
입력
첫째 줄에 N이 주어진다.
출력
놓을 수 있는 비숍의 최대 개수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 | 2 |
풀이
비숍은 대각선으로만 이동하므로, 흰 칸과 검은 칸은 서로 독립이다. 수학 공식으로 답을 구한다.
- N이 1이면 비숍은 1개만 놓을 수 있다
- N이 2 이상이면 최대
2 * (N - 1)개를 놓을 수 있다
핵심 아이디어: 비숍의 대각선 공격 특성상, 같은 색 칸의 각 대각선 줄에 최대 1개씩 배치할 수 있어 답이 2*(N-1)이 된다.
코드
n = int(input())
if n == 1:
print(1)
else:
print(n * 2 - 2)복잡도
- 시간: O(1) — 수학 공식 계산
- 공간: O(1) — 상수 변수만 사용