방공호 만들기

시간 제한1초메모리 제한1024 MB

요약

한 변의 길이가 1인 정사각형 벽 N개로 완전히 둘러싼 직사각형 방공호의 최대 넓이를 구한다. 각 벽은 둘레 1만큼을 담당한다.

난이도: 보통10점 중 7점
유형: 수학, 그리디, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

한 변의 길이가 $1$ 인 정사각형 모양의 벽 $N$ 개를 서로의 변과 평행하게, 겹치지 않도록 설치하여 최대한 넓은 방공호를 만들려고 한다. 방공호의 넓이를 벽으로 완전히 둘러싸인 내부 공간의 바닥 넓이로 정의할 때, $N$ 개의 벽으로 만들 수 있는 방공호의 최대 넓이를 구해보자.

벽 $7$ 개를 아래와 같이 설치하면 넓이 $3$ 을 가지는 방공호를 만들 수 있다. 이보다 큰 넓이의 방공호는 만들 수 없다.

입력

첫째 줄에 벽의 개수 $N$ 이 주어진다. $\left(1\leq N\leq 10,000,000\right)$

출력

벽 $N$ 개로 만들 수 있는 방공호 넓이의 최댓값을 출력한다.

예제4

예제 1
입력
```
4
```
예상 출력
```
1
```
예제 2
입력
```
5
```
예상 출력
```
1
```
예제 3
입력
```
6
```
예상 출력
```
2
```
예제 4
입력
```
7
```
예상 출력
```
3
```