26005번 - 나뭇잎 학회

문제

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

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

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

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

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

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

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

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

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

입력

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

출력

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

제한

힌트

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

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

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

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

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

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

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

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

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

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

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

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

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

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