나뭇잎 학회

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

요약

N×N 격자에서 전구에 연결된 스위치를 모든 경우에 찾아내는 데 필요한 인접 스위치 쌍 누르기 횟수의 최솟값을 구합니다.

문제

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

보이는 것과 같이 전구 하나와 $N \times N$ 개의 스위치가 $N \times N$ 배열로 놓여 있습니다.
이 스위치 중 하나만 전구와 연결되어 있으며, 연결된 스위치를 누르면 전구가 깜빡입니다.
스위치에는 특수 장치가 적용되어 있어서 상하좌우로 인접한 두 개의 스위치를 동시에 눌러야만 합니다.
예를 들어 $N=3$ 일 때, $5$ 번 스위치를 누르고 싶다면 인접한 스위치 상( $2$ ), 하( $8$ ), 좌( $4$ ), 우( $6$ ) 중 하나와 함께 한 번에 눌러야 합니다.
전구와 연결된 스위치가 어느 것인지 알아내서 답을 제출해야 합니다.

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

귀찮은 일을 싫어하는 기선이는 밖에서 나뭇잎을 최소한만 주워 오려고 한다. 어떤 경우에도 정답을 맞히는 데 필요한 나뭇잎의 최소 개수를 구하여라.

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

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

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

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

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

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

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

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

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

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

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

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