Hanoi Tower라는 유명한 문제가 있다. 하노이 사원에는 3개의 막대가 있고 그중 하나의 막대에 3게의 크기가 서로 다른 n개의 둥근 원반이 끼워져 있다. 한 막대에 n개의 원반이 전부 꽃아져있고 각각의 원반은 자신보다 작은 원반 위에 있을 수 없다고 할때 n개의 원반을 다른 막대로 옮기는데 거리는 횟수를 구하는 문제다. #include <iostream> #include <windows.h> #include <vector> using namespace std; int n,c; vector<int> a[3]; void print_stacks_state(); void movestack(int h, bool isRight,int i){ //i에 있는h높이의 탑을 오른쪽 또는 왼쪽으로 옮기는 것을 //h-1높이의 탑을 옮기는 것으로 표현. //i칸에서 윗부분 h-1높이의 탑을 다른 칸으로 옯긴후 밑의 h번째 블락을 원하는 //칸으로 옮긴후 그 칸으로 다른곳이 임시로 옮겨놓은h-1높이의 칸을 다시 옮긴다. //n 높이의탑을 옮길때 (n-1높이의 탑을 옮길때 움직인 횟수)*2+1만큼 든다. //따라서, 높이 1의 탑을 옮길 때 1의 횟수가 필요하므로 n일때는 //2^(n-1)+2^(n-2)+...4+2+1이다 //=등비가 2인 n개의 등비수열의 합=1*(2^n-1)/(2-1)=(2^n)-1 if(h==1){ ...