보스 배틀

시간 제한2초메모리 제한512 MB

요약

원형으로 놓인 n개의 기둥 뒤에 숨은 보스를 잡아야 한다. 폭탄은 한 기둥과 양옆 기둥을 공격하고 보스는 매 턴 한 칸까지 움직일 수 있을 때, 최악의 경우에도 잡는 최소 폭탄 수를 구한다.

문제

좋아하는 비디오 게임의 보스 스테이지에서 막혔다. 보스전은 원형 방에서 벌어진다. 방 둘레에는 부술 수 없는 기둥 $n$ 개가 일정한 간격으로 서 있다. 보스는 그중 한 기둥 뒤에 숨는데, 어느 기둥인지는 알 수 없다. 그다음부터 나와 보스가 번갈아 행동한다.

내 차례에는 기둥 하나를 골라 그 옆으로 폭탄을 던질 수 있다. 보스가 그 기둥 뒤에 있거나 그 기둥과 이웃한 두 기둥 중 하나의 뒤에 있으면 보스는 쓰러진다.

보스가 쓰러지지 않았으면 보스의 차례다. 보스는 있던 자리에 그대로 있거나, 지금 있는 기둥과 이웃한 기둥으로 옮겨 갈 수 있다. 폭발 연기 때문에 이 움직임은 보이지 않는다.

지난번에는 폭탄이 떨어져서 보스를 잡지 못했다. 이번에는 보스가 어떻게 행동하더라도 반드시 잡을 만큼 폭탄을 챙기려고 한다. 최악의 경우에도 보스를 쓰러뜨리려면 폭탄이 최소 몇 개 필요한지 구하라.

아래 그림은 $n = 4$ 인 경우의 예다. 이때는 폭탄 2개로 충분하다. 회색 기둥은 보스가 숨어 있을 수 없는 기둥이고, 검은색은 폭탄이다.

첫째 줄에 방에 있는 기둥의 수 $n$ 이 주어진다 ( $1 \le n \le 100$ ).

최악의 경우에 보스를 쓰러뜨리는 데 필요한 폭탄의 최소 개수를 출력한다.