백준11729 - 하노이 탑 이동 순서

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

재귀 호출에서 가장 기초가 되는 문제이다.

탑이 세 개가 존재하는데 첫번째 탑에 n개의 판이 작은 원판에서 큰 원판까지 꼭대기부터 바닥에 존재한다.

원판 n개를 최소 몇 번의 이동을 하여 첫번째 탑에서 마지막 탑으로 갈 수 있는지 묻는다.

원판의 최소 이동 횟수는 2^n - 1이다.

가장 기초가 되는 문제이니 꼭 집고 넘어가자.

 

#include <iostream>
#include <cmath>
using namespace std;


void move(int no, int x, int y) { //x에서 y기둥으로 접시 no개를 옮긴다.
	if (no > 1) { //첫째 기둥에서 중간 기둥으로 옮긴다.
		move(no - 1, x, 6 - x - y); 
	}
	cout << x << ' ' << y << '\n'; //x번에서 y번으로 이동했다는 것을 표시
	if (no > 1) {//중간 기둥에서 마지막 기둥으로 옮긴다.
		move(no - 1,6 - x - y, y);
	}
}


int main() {
	int no; //원판의 갯수
	long long int cnt; //이동횟수를 셀 변수


	cin >> no;
	cnt = pow(2, no) - 1; //최소 이동횟수는 2^n - 1, cmath의 pow함수 이용
	cout << cnt << '\n';
	
    
	move(no, 1, 3);
}