일반적인 하노이 탑에서 n개의 원판을 옮기 려면 n-1개의 원판을 미리 옮겨 논 이후에 1개의 원판의 옮긴 이후 다시 n-1개의 원판을 옮기는 형식. 즉 P(n) = 2*P(n-1)+1 이라는 점화식을 만들 수 있습니다.

그렇다면 기둥이 4개인 하노이 탑에서는 P(n) = 2*P(n-2)+3 이라는 점화식이 만들어 지는것이 아닌가요?

즉, 1번기둥에서 4번 기둥으로 n개의 원판을 옮기기 위해 우선 1번 기둥에서 2번 기둥에 n-2개의 원판을 이동시킨 이후 남은 두개의 원판을 3번과 4번을 이용해 옮기면 3번의 이동이 필요 합니다. 그러므로 위의 점화식을 유추할 수 있다고 생각합니다.

문제에서 long long 으로 출력할 수있다고 해서 풀어 본 결과 굉장히 큰 수가 나오더군요.

아래는 파이썬으로 간단하게 짠 코드 입니다만, 

입력값이 1000일 경우  9820171823688425610039569090482797456649926138129194368449874104288401389214023664649810276977712471452660052382680213027651769637656179159985582768125라는 어마 무시한 숫자가 나오는데 어디가 문제 인지 알려 주시면 감사하겠습니다.