전구

1891년 아인트호번(Eindhoven)에 전구 회사를 세운 Frederik Philips는 얼마 지나지 않아 발견을 하나 했다. 수평 또는 수직 방향으로 무한히 뻗는 빛을 내는 전구였다. 그는 이 발견으로 현대 주택의 실내 디자인을 바꾸려 한다.

그는 아들 Gerard와 정교한 설치 계획을 세운다. 방 안에 $N \times N$ 격자 모양으로 $N^2$개의 전구를 설치한다. 전기를 아끼려고 켜는 전구를 가능한 한 적게 써서 방 전체를 밝히려 한다. 각 전구는 수직 또는 수평이다. 수직 전구는 자신이 속한 열의 모든 칸을, 수평 전구는 자신이 속한 행의 모든 칸을 밝힌다.

아래 그림은 수직 전구(왼쪽)와 수평 전구(오른쪽)를 보여준다.

실험에서 Frederik은 다른 방에서 각 전구를 켜고 끄며, Gerard는 불이 켜진 칸의 총 개수를 보고한다. 두 개 이상의 전구가 비추는 칸은 한 번만 센다. 실험 중에 켜는 전구의 수는 상관없지만, 실험 횟수는 가능한 한 적어야 한다.

두 사람이 방 전체를 밝히면서 사용하는 전구 수가 가장 적은 배치를 찾도록 도와라.

• $3 \le N \le 100$.
• 실험은 최대 $2\,000$번까지 할 수 있다. 최종 답을 출력하는 것은 실험 횟수에 포함되지 않는다. 이를 넘으면 '틀렸습니다(Wrong Answer)' 판정을 받는다. 실험 횟수가 적을수록 높은 점수를 받는다.