개구리가 연못 위에서 놀고 있다. 개구리는 N개의 연잎 들을 이용해서 이리저리 뛰어놀고 있다.

개구리가 뛰는 장면을 보던 강빈이는 개구리가 도약을 하는 경우가 얼마나 있는지 궁금해졌다. 여기서 도약은 아래 조건을 만족하는 경우를 말한다.

1. 개구리가 뛴 거리가 이전에 뛴 거리 이상 뛰지만 그 2배보다 멀리 뛰지는 않는다. 2. 개구리는 오른쪽으로만 뛴다. 3. 개구리는 두 번만 뛴다. 4. 위 세 가지 조건을 만족한다면 어느 곳에서든 시작할 수 있다.

허나, 연잎들이 너무 많기 때문에 가능한 횟수가 매우 많아질 것 같다고 생각한 강빈이는, 개구리가 오른쪽으로 도약하는 경우가 얼마나 되는지 구해달라고 했다. 강빈이를 위해 프로그램을 짜주자.

도약 timer 1s memory 64MB

도약 1s 64MB