11729번-하노이 탑 이동 순서

#include<bits/stdc++.h>
using namespace std;

void func(int i,int j, int n) {
	if (n == 1) {
		cout << i << ' ' << j<<"\n";
		return;
	}
	func(i, 6 - i - j, n - 1);
	cout << i << ' ' << j<<"\n";
	func(6 - i - j, j, n - 1);
}

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	cout << (1 << n) - 1<<"\n";
	func(1, 3, n);
}

위의 풀이를 볼때 func에 들어갈 수를 1,2,4->1,3,3...뭐 이런식으로 절차적으로 생각하면 답도 없다. 

재귀는 무조건 n=1일 때 ok. n-1일때 성립하면 n도 성립. 이런식으로 귀납적으로 생각해야한다. 

 

- 파이썬

def func(a,b,n):
    if n==1:
        print(a,b)
        return
    func(a,6-a-b,n-1)
    print(a,b)
    func(6-a-b,b,n-1)

n=int(input())
print(2**n-1)
func(1,3,n)