미스터 미야기의 지구 침략 일지

콰크고 제국 원정군은 지구 침략을 노리는 악의 조직이다. 그들은 침략자의 전통에 따라 일본 도쿄 주변을 목표로 매주 1체씩 괴인을 보내왔다. 그러나 그때마다 인류전대 어스파이브라는 5명의 전사가 나타나, 거리에서 날뛰던 괴인은 손쉽게 쓰러지고 말았다.

와르자드 스루(지구명: 미나모토 마사)는 이런 현실을 진심으로 걱정하는 콰크고 제국 원정군의 여간부다. 그녀는 매주의 패배에서 아무것도 배우려 하지 않는 사령관과, 어딘가 어긋난 발명을 반복하는 천재 과학자들 밑에서 골치 아픈 나날을 보내고 있었다.

그러던 중 다음 작전은 흡혈 괴인 드라큘라스를 일본에 보내는 것으로 정해졌다. 드라큘라스는 피를 빨아들인 인간을 드라큘라스로 바꿔버리는 무서운 괴인이다. 드라큘라스에게 피를 빨린 인간 역시 다른 인간의 피를 빨아 동료 드라큘라스를 늘려간다. 이렇게 지구 전역을 드라큘라스로 메워버리려는 작전이다.

이를 들은 와르자드는 곧바로 깨달았다. 이 작전은 유치원 버스 납치 같은 평소의 하찮은 작전과는 차원이 다르다. 저 못난 사령관이 세운 것치고는 드물게, 정말로 지구를 정복할 가능성을 품고 있다고.

배로 불어나는 게임의 기세는 무섭다. 지상에 내려선 드라큘라스는 순식간에 동료 수를 늘려갔다. 이대로라면 지구 침략은 코앞이라고 여겨졌다. 그러나 그 순간, 와르자드의 머릿속을 강렬한 불길한 예감이 스쳐 지나갔다. 설마, 이 괴인, 오리지널이 쓰러지면 동료도 전멸하는 건 아니겠지?

급히 드라큘라스를 설계 개발한 과학자를 추궁하자, 역시 와르자드가 걱정한 대로였다. 오리지널 드라큘라스가 당하면 피를 빨린 인간은 모두 원래대로 돌아가도록 설계되어 있다는 것이다. 개발자 이 자식아. 왜 그런 쓸데없는 기능을 넣은 거야!

와르자드는 개발 담당자에게 날아차기를 먹이고, 곧바로 오리지널 회수 작업에 착수했다. 아무리 오리지널과 가짜가 겉모습이 완전히 같다고 해도, 이대로는 달려온 어스파이브에게 어떤 이유로든 오리지널을 간파당해 패배하는 것이 눈에 보인다.

개발자의 말에 따르면 드라큘라스가 된 인간의 무게는 모두 같지만, 오리지널 드라큘라스는 그것보다 조금 더 무겁다고 한다. 그렇다면 천칭저울을 쓰면 오리지널을 찾을 수 있을 것이다. 어스파이브가 나타나기 전에, 되도록 빨리 오리지널 드라큘라스를 찾아 회수해야 한다.

N

입력의 첫째 줄에 정수 N(2 ≤ N ≤ 2,000,000,000)이 주어진다. 이는 오리지널과 가짜를 합한 드라큘라스의 수를 나타낸다.

천칭저울을 사용해 N체의 드라큘라스 중에서 1체의 오리지널을 찾으려면, 최악의 경우에도 천칭저울을 몇 번 사용하면 충분한가. 그 최솟값을 출력하라. 단, 천칭저울의 왼쪽 접시와 오른쪽 접시에 각각 몇 체의 드라큘라스를 올려 무게를 비교하는 것을 1회로 센다.