P1914

[baekjoon-1914] 하노이 탑

풀이 과정

하노이 탑은 대표적인 재귀 문제이다. 아래의 그림을 보면 재귀라는 것을 단번에 알 수 있다.

이 문제는 재귀 뿐만 아니라 큰 수에 대한 연산 처리가 필요한 문제이다. N의 크기는 100이며, 하노이 탑의 실행 횟수는 2^N-1이다. 그럼 최대 2^100까지 연산이 필요한데, 2^100은 long으로도 처리할 수 없는 큰 수이다. (long은 64비트) 따라서 java.math.BigInteger를 사용해 풀었다.

new BigInteger("2").pow(N).subtract(new BigInteger("1"))