문제 해결 전략

• 완전한 크기의 알약과 반절 크기의 알약 둘 중 하나를 선택하면서 진행되는 경우의 수 문제이다.

• 매순간 2번을 선택할 수 있으므로, n은 30인데...
  그런데 손녀는 2n이 지나서야 끝난다.

• 왜냐하면 완전한 알을 선택하면 반절로 쪼개지니까.
  완전한 알의 개수가 half 알로 증가하기 때문이다.

• 예를 들어 알이 1개 있다고 하면
  완전한 1알이 반절짜리 알이 1개 생성된다. 그리고 완전한 1알 제거.
  이후에는 반절짜리 1개이므로 다음 턴에 제거된다.

• 즉 2의 60승 만큼 진행해야 하는데, 시간복잡도 불가하므로,
  메모이제이션 사용이다.

-> 변경되는 거는 완전한 알의 개수와 half 알의 개수이다.

생각해보기

• 혹시나 겹치는 상황이 발생하지 않을까? 생각하지만, 매순간 2번의 선택이 발생하기 때문에 상관할 필요 없다.

• 완전한 크기 알을 선택하면 완전한 -1 하고, 반절 알은 +1 해야 한다.

• 반절 크기 알을 선택하면 반절 크기만 -1 한다.

• 기저 사례는 완전한 크기의 알과 반절 크기 알 모두 소모했을 때이다.