참새 timer 1s memory 32MB

여러분은 가장 강력한 동물이 무엇이라고 생각하는가?

아마도 호랑이나 사자, 코끼리를 떠올릴 것 같다.

하지만 "참새" 가 이들보다 강력할지도 모른다.

참새는 무려 날 수 있기 때문이다.

물론 참새가 항상 날지는 않고 보통은 바닥에서 총총 뛰어다닌다.

여러분은 참새 한 마리가 N 발자국 총총 뛰어다닌 바닥을 보고 있다.

참새는 한 번 뛰면 양 발로 정확히 같은 깊이의 두 자국을 남기고, 이렇게 새겨진 두 자국은 다른 자국과는 항상 깊이가 다르다.

따라서 바닥에는 총 2N개의 자국이 있게 되었다.

그런데 옆에서 구경하던 문홍윤 멘토가 실수로 자국 하나를 지워 버렸다!

이제 바닥에는 총 2N-1개의 자국이 있고 그 깊이를 모두 재보았다.

문홍윤 멘토가 지워버린 자국의 깊이가 얼마인지 맞춰보자.