시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB31721317666.920%

문제

기선이는 퀴즈를 좋아해서 알고리즘 학회에 들어가고자 하이아크에 방문하였다. 하지만 학회 문 앞에는 단 한 개의 전구, 여러 개의 스위치와 함께 다음과 같은 쪽지가 붙어있었다.

  • 보이는 것과 같이 하나의 전구와 $N \times N$ 개의 스위치가 $N \times N$ 배열로 있습니다.

  • 이 스위치 중 단 하나만 전구와 연결되어 있으며, 연결된 스위치를 누르면 전구가 깜빡입니다.

  • 스위치에는 특수 장치가 적용되어 있어서 상하좌우로 인접한 두 개의 스위치를 동시에 눌러야만 합니다.

  • 예를 들어 $N=3$일 때, 당신이 $5$번 스위치를 누르고 싶다면 인접한 스위치 상($2$), 하($8$), 좌($4$), 우($6$) 중 하나의 스위치와 같이 한 번에 눌러야 합니다.

  • 당신은 전구와 연결된 스위치가 어느 것인지 알아내서 답을 제출해야 합니다.

'너무 쉽잖아' 생각하고 스위치를 누르려는 순간, 밑에 작게 쓰여있는 글씨를 보고 경악하고 말았다.

  • 단, 두 개의 스위치를 한 번에 누를 때마다 나뭇잎 하나를 문틈으로 제출해야 합니다.

귀찮음이 많은 기선이는 밖에서 최소한의 나뭇잎만 주워오려고 한다. 어떤 경우에도 정답을 맞히는 데 필요한 나뭇잎의 최소 개수를 여러분이 대신 구해보자.

입력

$N$ 이 주어진다. ($1 \le N \le 1\,000$)

출력

어떤 경우에도 정답을 맞히는 데 필요한 나뭇잎의 최소 개수를 출력한다.

예제 입력 1

1

예제 출력 1

0

스위치가 하나라면 눌러보지 않아도 전구가 해당 스위치와 연결되어 있다는 사실을 알 수 있다. 

예제 입력 2

2

예제 출력 2

2

예제 입력 3

3

예제 출력 3

5

예제 입력 4

4

예제 출력 4

8

힌트

$N=2$ 일 때는 다음과 같다.

ⅰ) 전구가 $1$번 스위치와 연결되어 있는 경우

  1. $3$번 스위치와 $4$번 스위치를 누른다. 전구가 깜빡이지 않는다.
  2. $2$번 스위치와 $4$번 스위치를 누른다. 전구가 깜빡이지 않는다.

$2$번, $3$번, $4$번 스위치를 눌렀으나 전구가 깜빡이지 않았으므로 $1$번 스위치가 전구와 연결되어 있다는 사실을 알 수 있다.

ⅱ) 전구가 $2$번 스위치와 연결되어 있는 경우

  1. $3$번 스위치와 $4$번 스위치를 누른다. 전구가 깜빡이지 않는다.
  2. $2$번 스위치와 $4$번 스위치를 누른다. 전구가 깜빡인다.

$2$번 스위치가 전구와 연결되어 있다는 사실을 알 수 있다.

ⅲ) 전구가 $3$번 스위치와 연결되어 있는 경우

  1. $3$번 스위치와 $4$번 스위치를 누른다. 전구가 깜빡인다.
  2. $2$번 스위치와 $4$번 스위치를 누른다. 전구가 깜빡이지 않는다.

$3$번 스위치가 전구와 연결되어 있다는 사실을 알 수 있다.

ⅳ) 전구가 $4$번 스위치와 연결되어 있는 경우

  1. $3$번 스위치와 $4$번 스위치를 누른다. 전구가 깜빡인다.
  2. $2$번 스위치와 $4$번 스위치를 누른다. 전구가 깜빡인다.

$4$번 스위치가 전구와 연결되어 있다는 사실을 알 수 있다.

전구가 $1$번, $2$번, $3$번, $4$번 중 어떤 스위치와 연결되어 있든 최대 2개의 나뭇잎으로 전구의 위치를 찾을 수 있으니 필요한 나뭇잎의 최소 개수는 2개이다.