하노이의탑 하는법

6개의 원판을 세개의 기둥을 이용해서 옮기는 문제!
단, 큰 원판은 작은 원판위에 올라갈수 없다!

누구나 한번 봤을법한 하노이의 탑 문제입니다.

원리만 알면 쉽게 풀어 낼 수 있다는데

아무리봐도 모르겠습니다.
최소 횟수는 63이라는데.. 한번도 완성을 못하니..

그러다 곰곰히 생각 해보니 문제가 풀렸습니다.

생각흐름
- 리듬이 있다. 가작 작은 원판 기준으로 한칸씩 이동해가는데 세개의 기둥이 연결된 긴 선 상에 있다고 생각하면 쉽다.

- 하나를 가장 오른쪽으로 보내고 남은 기둥에 보내진 원판 외에 나머지 원판을 차례대로 쌓고 진행한다

 

컴퓨터공학과 학생들은 알고리즘의 재귀에서 보게되는 문제죠.

 

300번 이동해서 겨우 맞췄는데 순식간에 100번 이내로 돌파! 뿌듯하네요