하노이 타워 1

문제 설명

서로 다른 n개의 원판과 세 개의 기둥이 있는 하노이 타워가 있습니다. 모든 원판은 크기가 큰 것이 아래로 오도록 순서대로 쌓여 1번 기둥에 놓여 있으며, 다음과 같은 이동 규칙을 따릅니다.

1. 한 번에 하나의 원판만 옮길 수 있습니다.
2. 각 기둥의 맨 위에 있는 원판만 이동할 수 있습니다.
3. 작은 원판 위에 큰 원판을 올려놓을 수 없습니다.

원판의 개수 n이 주어졌을 때, 위의 이동 규칙을 따라 1번 기둥에 있는 모든 원판을 3번 기둥으로 옮기기 위해 필요한 최소 이동 횟수를 반환하는 solution 함수를 작성하시오.

제한 사항

• n은 1 이상 20 이하의 자연수입니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• n이 1인 경우, 원판을 1번 기둥에서 3번 기둥으로 바로 옮길 수 있으므로 1을 반환합니다.

2번 테스트케이스 설명

• n이 3인 경우, 이동 규칙에 따라 최소 7번의 이동이 필요합니다.
  이동 순서는 다음과 같습니다:
  크기 1 원판 : 1 -> 3
  크기 2 원판 : 1 -> 2
  크기 1 원판 : 3 -> 2
  크기 3 원판 : 1 -> 3
  크기 1 원판 : 2 -> 1
  크기 2 원판 : 2 -> 3
  크기 1 원판 : 1 -> 3

• 총 7번의 이동이므로 7을 반환합니다.

3번 테스트케이스 설명

• n이 5인 경우, 이동 규칙에 따라 최소 31번의 이동이 필요합니다.