백준/11729/Recursion/하노이 탑 이동 순서

백준/11729/Recursion/하노이 탑 이동 순서
대학교 알고리즘 수업에서 재귀를 배울 때 예시로 보았던 하노이 탑이다.
재귀 문제를 풀때마다 귀납적 사고를 하려고 하지만 잘 안된다.
해당 문제를 생각할 때 처음 생각한 재귀 방식은

1 ~ n-1까지 2번째 타워로 옮기면
n 번째 링을 3번째로 옮기면 된다.
이 후, 1~n-1까지를 2번째 타워에서 3번째로 옮기면 된다.

라는 가정을 세우고 함수를 세우려하니 타워 변수를 어떻게 둬야하나 고민했다.
출발지와 도착지를 제외하고 남아있는 타워로 옮겨야하는데 이를 어떻게 표현하지라는 생각때문에 오래 걸린 문제였다.

간단했다. 총합이 3+2+1 이니 6에서 도착지와 출발지에 대한 정보를 빼면 남은 타워였다.
이 후에 설계는 간단하다.

void func(int start,int dest,int num)
{
	if(num==1)
    {
    	cout<< start <<' '<< dest << endl;
    }
    // 1~n-1까지는 start와 dest를 제외한 타워로 이동
    func(start,6-start-dest,num-1);
    // 1~n-1까지 이동했으면 n을 start에서 dest로 이동
    cout<< start << ' ' << dest << endl;
    // n을 이동했으면 나머지 1~n-1도 dest로 이동
    func(6-start-dest, dest, num-1);
}

풀이

첫번째 풀이

#include<iostream>
using namespace std;

int N;

void solution(int, int, int);

void solution(int start,int dest,int num)
{
	if (num == 1)
	{
		cout << start << ' ' << dest << endl;
		return;
	}
	solution(start, 6 - dest - start, num - 1);
	cout << start << ' ' << dest << endl;
	solution(6 - dest - start, dest, num - 1);
}

int main()
{
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(0);
	cin >> N;
	solution(1,3,N);
}