하노이의 탑 점화식이 

 x(n) = 2*x(n-1) + 1


인데 딱봐도 등비수열이잖아. 그래서 계산해보면


x(n) = 2^n-1

이렇게 나오네


uint64_t numTowerOfHanoi(uint64_t n) { 

  return (1 << n) - 1;

}


이렇게 하면 상수시간에 계산 끝나네 ㅇㅅㅇ